Split graph

In

Hammer (1977a, 1977b), and independently introduced by Tyshkevich and Chernyak (1979), where they called these graphs "polar graphs" (Russian: полярные графы).^[1]

A split graph may have more than one partition into a clique and an independent set; for instance, the path $a - b - c$ is a split graph, the vertices of which can be partitioned in three different ways:

the clique ${a, b}$ and the independent set ${c}$
the clique ${b, c}$ and the independent set ${a}$
the clique ${b}$ and the independent set ${a, c}$

Split graphs can be characterized in terms of their

forbidden induced subgraphs: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle).^[2]

Relation to other graph families

From the definition, split graphs are clearly closed under

star graphs.^[5] Almost all chordal graphs are split graphs; that is, in the limit as n goes to infinity, the fraction of n-vertex chordal graphs that are split approaches one.^[6]

Because chordal graphs are

Strong Perfect Graph Theorem

.

If a graph is both a split graph and an interval graph, then its complement is both a split graph and a comparability graph, and vice versa. The split comparability graphs, and therefore also the split interval graphs, can be characterized in terms of a set of three forbidden induced subgraphs.^[7] The split cographs are exactly the threshold graphs. The split permutation graphs are exactly the interval graphs that have interval graph complements;^[8] these are the permutation graphs of skew-merged permutations.^[9] Split graphs have cochromatic number 2.

Algorithmic problems

Let $G$ be a split graph, partitioned into a clique $C$ and an independent set $i$ . Then every

maximum independent set in a split graph. In any split graph, one of the following three possibilities must be true:^[10]

There exists a vertex $x$ in $i$ such that $C \cup {x}$ is complete. In this case, $C \cup {x}$ is a maximum clique and $i$ is a maximum independent set.
There exists a vertex $x$ in $C$ such that $i \cup {x}$ is independent. In this case, $i \cup {x}$ is a maximum independent set and $C$ is a maximum clique.
$C$ is a maximal clique and $i$ is a maximal independent set. In this case, $G$ has a unique partition $(C, i)$ into a clique and an independent set, $C$ is the maximum clique, and $i$ is the maximum independent set.

Some other optimization problems that are

NP-complete for split graphs.^[12]

Degree sequences

One remarkable property of split graphs is that they can be recognized solely from their

degree sequences

. Let the degree sequence of a graph

G

be

d 1 \geq d 2 \geq \dots \geq d n

, and let

m

be the largest value of

i

such that

d i \geq i - 1

. Then

G

is a split graph if and only if

\sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.

If this is the case, then the $m$ vertices with the largest degrees form a maximum clique in $G$ , and the remaining vertices constitute an independent set.[13]

The splittance of an arbitrary graph measures the extent to which this inequality fails to be true. If a graph is not a split graph, then the smallest sequence of edge insertions and removals that make it into a split graph can be obtained by adding all missing edges between the $m$ vertices with the largest degrees, and removing all edges between pairs of the remaining vertices; the splittance counts the number of operations in this sequence.^[14]

Counting split graphs

Sperner families. Using this fact, he determined a formula for the number of nonisomorphic

split graphs on n vertices. For small values of n, starting from n = 1, these numbers are

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (sequence A048194 in the OEIS).

This enumerative result was also proved earlier by Tyshkevich & Chernyak (1990).

Notes

complements of bipartite graphs (that is, graphs that can be partitioned into two cliques). Földes & Hammer (1977b) use the definition given here, which has been followed in the subsequent literature; for instance, it is Brandstädt, Le & Spinrad (1999)
, Definition 3.2.3, p.41.

^ Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.

^ Golumbic (1980), Theorem 6.1, p. 150.

^ Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151; Brandstädt, Le & Spinrad (1999), Theorem 3.2.3, p. 41.

^ McMorris & Shier (1983); Voss (1985); Brandstädt, Le & Spinrad (1999), Theorem 4.4.2, p. 52.

^ Bender, Richmond & Wormald (1985).

^ Földes & Hammer (1977b); Golumbic (1980), Theorem 9.7, page 212.

^ Brandstädt, Le & Spinrad (1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.

^ Kézdy, Snevily & Wang (1996).

^ Hammer & Simeone (1981); Golumbic (1980), Theorem 6.2, p. 150.

^ Müller (1996)

^ Bertossi (1984)

^ Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow & Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt, Le & Spinrad (1999), Theorem 13.3.2, p. 203. Merris (2003) further investigates the degree sequences of split graphs.

^ Hammer & Simeone (1981).

References

Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221,
MR 0770128
.

Bertossi, Alan A. (1984), "Dominating sets for split and bipartite graphs", doi:10.1016/0020-0190(84)90126-1
.

ISBN 0-89871-432-X
.

MR 2233847
.

Földes, Stéphane;
MR 0505860
.

Földes, Stéphane;
MR 0463041
.

MR 0562306
.

MR 0637832
.

Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), "Partitioning permutations into increasing and decreasing subsequences", MR 1370138
.

McMorris, F. R.; Shier, D. R. (1983), "Representing chordal graphs on K_1,n", Commentationes Mathematicae Universitatis Carolinae, 24: 489–494,
MR 0730144
.

Merris, Russell (2003), "Split graphs", MR 1975945
.

Müller, Haiko (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", doi:10.1016/0012-365x(95)00057-4
.

MR 1778996
.

MR 0587712

MR 0554162
.

doi:10.1007/BF01240267
.

MR 0689420
.

Voss, H.-J. (1985), "Note on a paper of McMorris and Shier", Commentationes Mathematicae Universitatis Carolinae, 26: 319–322,
MR 0803929
.

Further reading

A chapter on split graphs appears in the book by Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs".

Retrieved from "https://en.wikipedia.org/w/index.php?title=Split_graph&oldid=1254260054"

[1] ts of bipartite graphs (that is, graphs that can be partitioned into two cliques). Földes & Hammer (1977b) use the definition given here, which has been followed in the subsequent literature; for instance, it is Brandstädt, Le & Spinrad (1999)
, Definition 3.2.3, p.41.

[2] Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.

[3] Golumbic (1980), Theorem 6.1, p. 150.

[4] Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151; Brandstädt, Le & Spinrad (1999), Theorem 3.2.3, p. 41.

[5] McMorris & Shier (1983); Voss (1985); Brandstädt, Le & Spinrad (1999), Theorem 4.4.2, p. 52.

[6] Bender, Richmond & Wormald (1985).

[7] Földes & Hammer (1977b); Golumbic (1980), Theorem 9.7, page 212.

[8] Brandstädt, Le & Spinrad (1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.

[FOOTNOTEKézdySnevilyWang1996-9] Kézdy, Snevily & Wang (1996).

[10] Hammer & Simeone (1981); Golumbic (1980), Theorem 6.2, p. 150.

[11] Müller (1996)

[12] Bertossi (1984)

[13] Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow & Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt, Le & Spinrad (1999), Theorem 13.3.2, p. 203. Merris (2003) further investigates the degree sequences of split graphs.

[FOOTNOTEHammerSimeone1981-14] Hammer & Simeone (1981).

[1]

[2]

[5]

[6]

[7]

[8]

[9]

[10]

[12]

[14]