10
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Unfortunately "split cluster graphs" seems to be in use for a different concept (graphs in which each connected component is split). $\endgroup$
    – David Eppstein
    May 5, 2015 at 18:12

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 at 16:17
7
$\begingroup$

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."

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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