TOPICS
Search

Split Graph


A split graph is a graph whose vertices can be partitioned into a clique and an independent vertex set.

Equivalently, it is a chordal graph whose graph complement is also chordal (Royle 2000). Royle (2000) also proved that there is a one-one correspondence between the split graphs on n vertices and the minimal covers of a set of size n.

Classes of graphs that are split include complete K_n, empty K^__n, star, and sun graphs.

Since all chordal graphs are perfect, so too are all split graphs.

Let d_1>=d_2>=...>=d_n be the degree sequence of a graph on n vertices, and let m be the largest value of i such that d_i>=i-1. Then the graph is a split graph iff

 sum_(i=i)^md_i=m(m-1)+sum_(i=m+1)^nd_i.

Furthermore, for a graph satisfying this condition, the vertices corresponding to the first m degrees in the degree sequence correspond to a maximum clique and the remainder to an independent vertex set (Golumbic 1980, Hammer and Simeone 1981).

SplitGraphForbiddenSubgraphs

A graph is a split graph iff it does not contain any of the graphs C_5, C_4, and C^__4=2P_2 as a forbidden induced subgraph, where C_n is a cycle graph, G^_ is a graph complement, and 2P_2 is the 2-ladder rung graph (Mukhopadhyay et al. 2023).

The numbers of simple split graphs on n=1, 2, ... vertices are given by 1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (OEIS A048194).


See also

Chordal Graph, Clique, Degree Sequence, Maximum Clique, Minimal Cover

Explore with Wolfram|Alpha

References

Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.Hammer, P. L. and Simeone, B. "The Splittance of a Graph." Combinatorica 1, 275-284, 1981.Mukhopadhyay, A.; John, D.; and Vasudevan, S. "Recognizing and Generating Unswitchable Graphs." 12 Apr 2023. https://arxiv.org/abs/2304.12381.Royle, G. F. "Counting Set Covers and Split Graphs." J. Integer Seq. 3, Article 00.2.6, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.Sloane, N. J. A. Sequence A048194 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Split Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SplitGraph.html

Subject classifications