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:

cluster-split graph

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

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.

  • $\begingroup$ Thanks, Bart. It doesn't exactly roll off the tongue, but I guess it'll have to do. $\endgroup$
    – Pål GD
    May 7 '15 at 9:01
  • $\begingroup$ What about independent split graph? Or would that be likely to be confused with something else? $\endgroup$
    – Pål GD
    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."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.