graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, 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 discre ...

in which the vertices can be partitioned into a

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

and an independent set. Split graphs were first studied by , and independently introduced by . 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 * Desire p ...

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 subgraph In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...

s: a graph is split if and only if no

induced subgraph In the mathematical field of 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. Defini ...

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 graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...

s the complements of which are also chordal. Just as chordal graphs are the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

s 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 amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...

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 In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Int ...

, then its complement is both a split graph and a

comparability graph In graph 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, partially orderable 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. The split

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s are exactly the

threshold graph In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: # Addition of a single isolated vertex to the graph. # Addition of a single dominating vertex t ...

s. The split

permutation graph In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be d ...

s are exactly the interval graphs that have interval graph complements; these are the permutation graphs of

skew-merged permutation In the theory of permutation patterns, a skew-merged permutation is a permutation that can be partitioned into an increasing sequence and a decreasing sequence. They were first studied by and given their name by . Characterization The two smallest ...

s. 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 the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...

in a split graph is either itself, or the

neighborhood A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...

of a vertex in . Thus, it is easy to identify the maximum clique, and complementarily the

maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...

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, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

on more general graph families, including

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

, are similarly straightforward on split graphs. Finding a

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

remains

even for split graphs which are

strongly chordal graph In the mathematical area of graph theory, an undirected graph is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in has an ''odd chord'', i.e., an edge that connects two vertices that are an odd distance (>1) a ...

s. It is also well known that the Minimum Dominating Set problem remains

for split graphs.

Degree sequences

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

degree sequence In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is deno ...

s. 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 :

\sum_^m d_i = m(m-1) + \sum_^n d_i.

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 ''n''-vertex split graphs with ''n'' are in

one-to-one correspondence In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

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