# Name the graph class: Disjoint union of a clique and an independent set

Let $G$ be a graph which is the disjoint union of a clique and an independent set, i.e. $$G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} .$$

The graph class of all such graphs is characterized by the forbidden induced subgraphs set $\mathcal{H} = \{2K_2, P_3\}$ and is thus the intersection of a cluster graph and a split (or threshold) graph.

Does this (very simple) graph class have a name? I was unable to find the graph class on ISGCI, and the papers I know on the topic (e.g. Editing Simple Graphs and On the clique editing problem) do not refer to the class by a name.

Here is a figure of such a graph:

• Unfortunately "split cluster graphs" seems to be in use for a different concept (graphs in which each connected component is split). May 5 '15 at 18:12

## 2 Answers

The edge-complement of graphs in your class are complete split graphs: they can be partitioned into an independent set and a clique, such that every vertex in the independent set is adjacent to every vertex in the clique (see, for example, http://www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Hence you could call your graph class co-complete split graphs.

• Thanks, Bart. It doesn't exactly roll off the tongue, but I guess it'll have to do. May 7 '15 at 9:01
• What about independent split graph? Or would that be likely to be confused with something else? May 13 '15 at 16:17

In a recent article, Hüffner, Komusiewicz, and Nichterlein refer to this class as sparse split graphs. They also refer to the complement class, the complete split graphs, as dense split graphs.

Hüffner, Komusiewicz, and Nichterlein. "Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes."