science

Split graph

Split graph is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Split graph rather than just read about it. In short: 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: полярные графы).

Key takeaways

Split graph belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Split graph to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Split graph from memory before moving on to harder problems.

Reference excerpt

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: полярные графы). 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).

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 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 Chudnovsky et al. (2006) 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. 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 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:

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. 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. 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. It is also well known that the Minimum Dominating Set problem remains NP-complete 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 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

∑ i = 1 m d i = m ( m − 1 ) + ∑ i = m + 1 n d i . {\displaystyle \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. 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.

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 (1990).

Notes

References

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

Illustrations

Worked examples

Example 1 — a first encounter with Split graph

Start with the simplest possible case. Write down what Split graph claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Split graph before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Split graph ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Split graph

In research: Split graph appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Split graph in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Split graph is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph families, Intersection classes of graphs, Perfect graphs, so understanding it makes those chapters shorter.
In everyday life: Look for Split graph outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Split graph in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Split graph means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Split graph out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Split graph in simple terms?

Why does Split graph matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Split graph?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Split graph.