Split graph

From HandWiki
Short description: Graph which partitions into a clique and independent set
A split graph, partitioned into a clique and an independent set.

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and 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:

  1. the clique {a, b} and the independent set {c}
  2. the clique {b, c} and the independent set {a}
  3. 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 complementation.[3] Another characterization of split graphs involves complementation: they are chordal graphs the complements of which are also chordal.[4] Just as chordal graphs are the intersection graphs of subtrees of trees, split graphs are the intersection graphs of distinct substars of 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 perfect, so are the split graphs. The double split graphs, a family of graphs derived from split graphs by doubling every vertex (so the clique comes to induce an antimatching and the independent set comes to induce a matching), figure prominently as one of five basic classes of perfect graphs from which all others can be formed in the proof by (Chudnovsky Robertson) of the 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 maximal clique in a split graph is either C itself, or the neighborhood of a vertex in i. Thus, it is easy to identify the maximum clique, and complementarily the maximum independent set in a split graph. In any split graph, one of the following three possibilities must be true:[10]

  1. There exists a vertex x in i such that C ∪ {x} is complete. In this case, C ∪ {x} is a maximum clique and i is a maximum independent set.
  2. There exists a vertex x in C such that i ∪ {x} is independent. In this case, i ∪ {x} is a maximum independent set and C is a maximum clique.
  3. 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 on more general graph families, including graph coloring, are similarly straightforward on split graphs. Finding a Hamiltonian cycle remains NP-complete even for split graphs which are strongly chordal graphs.[11] It is also well known that the Minimum Dominating Set problem remains 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 d1 ≥ d2 ≥ … ≥ dn, and let m be the largest value of i such that di ≥ i – 1. Then G is a split graph if and only if

[math]\displaystyle{ \sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i. }[/math]

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

(Royle 2000) showed that (unlabeled) n-vertex split graphs are in one-to-one correspondence with certain 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).

Notes

  1. ↑ (Földes Hammer) had a more general definition, in which the graphs they called split graphs also included bipartite graphs (that is, graphs that be partitioned into two independent sets) and the complements of bipartite graphs (that is, graphs that can be partitioned into two cliques). (Földes Hammer) use the definition given here, which has been followed in the subsequent literature; for instance, it is (Brandstädt Le), Definition 3.2.3, p.41.
  2. ↑ (Földes Hammer); (Golumbic 1980), Theorem 6.3, p. 151.
  3. ↑ (Golumbic 1980), Theorem 6.1, p. 150.
  4. ↑ (Földes Hammer); (Golumbic 1980), Theorem 6.3, p. 151; (Brandstädt Le), Theorem 3.2.3, p. 41.
  5. ↑ (McMorris Shier); (Voss 1985); (Brandstädt Le), Theorem 4.4.2, p. 52.
  6. ↑ (Bender Richmond).
  7. ↑ (Földes Hammer); (Golumbic 1980), Theorem 9.7, page 212.
  8. ↑ (Brandstädt Le), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
  9. ↑ Kézdy, Snevily & Wang (1996).
  10. ↑ (Hammer Simeone); (Golumbic 1980), Theorem 6.2, p. 150.
  11. ↑ (Müller 1996)
  12. ↑ (Bertossi 1984)
  13. ↑ (Hammer Simeone); (Tyshkevich 1980); (Tyshkevich Melnikow); (Golumbic 1980), Theorem 6.7 and Corollary 6.8, p. 154; (Brandstädt Le), Theorem 13.3.2, p. 203. (Merris 2003) further investigates the degree sequences of split graphs.
  14. ↑ Hammer & Simeone (1981).

References

Further reading

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



Retrieved from "https://handwiki.org/wiki/index.php?title=Split_graph&oldid=3372100"