
In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a branch of mathematics, a split graph is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
in which the
vertices can be
partitioned into a
clique and an
independent set. Split graphs were first studied by , and independently introduced by , where they called these graphs "polar graphs" ().
A split graph may have more than one partition into a clique and an independent set; for instance, the
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desir ...
is a split graph, the vertices of which can be partitioned in three different ways:
#the clique and the independent set
#the clique and the independent set
#the clique and the independent set
Split graphs can be characterized in terms of their
forbidden induced subgraphs: a graph is split if and only if no
induced subgraph
In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset.
Definition
Formally, let G=(V,E) ...
is a
cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle).
Relation to other graph families
From the definition, split graphs are clearly closed under
complementation. Another characterization of split graphs involves complementation: they are
chordal graphs the
complements of which are also chordal. Just as chordal graphs are the
intersection graphs of subtrees of trees, split graphs are the intersection graphs of distinct substars of
star graphs.
Almost all
In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...
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.
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 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
In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partial ...
, 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. The split
cographs are exactly the
threshold graphs. The split
permutation graphs are exactly the interval graphs that have interval graph complements;
these are the permutation graphs of
skew-merged permutations. Split graphs have
cochromatic number 2.
Algorithmic problems
Let be a split graph, partitioned into a clique and an independent set . Then every
maximal clique in a split graph is either itself, or the
neighborhood
A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...
of a vertex in . 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:
# There exists a vertex in such that is complete. In this case, is a maximum clique and is a maximum independent set.
# There exists a vertex in such that is independent. In this case, is a maximum independent set and is a maximum clique.
# is a maximal clique and is a maximal independent set. In this case, has a unique partition into a clique and an independent set, is the maximum clique, and is the maximum independent set.
Some other optimization problems that are
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
on more general graph families, including
graph coloring
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
, are similarly straightforward on split graphs. Finding a
Hamiltonian cycle
In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
remains
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
even for split graphs which are
strongly chordal graphs. It is also well known that the Minimum Dominating Set problem remains
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
for split graphs.
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 be , and let be the largest value of such that . Then is a split graph if and only if
:
If this is the case, then the vertices with the largest degrees form a maximum clique in , and the remaining vertices constitute an independent set.
[; ; ; , Theorem 6.7 and Corollary 6.8, p. 154; , Theorem 13.3.2, p. 203. further investigates the degree sequences of split graphs.]
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 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.
Counting split graphs
showed that (
unlabeled) ''n''-vertex split graphs are in
one-to-one correspondence
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivale ...
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, ... .
This
enumerative result was also proved earlier by .
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*
*.
*. Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), ''Mathematical notes of the Academy of Sciences of the USSR'' 48 (6): 1239–1245, .
*.
*.
{{refend
Further reading
*A chapter on split graphs appears in the book by
Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs".
Graph families
Intersection classes of graphs
Perfect graphs