<p>In a recent article, Hüffner, Komusiewicz, and Nichterlein refer to this class as <strong>sparse&nbsp;split&nbsp;graphs</strong>.  They also refer to the complement class, the complete split graphs, as <em>dense&nbsp;split&nbsp;graphs</em>.</p>

<p>Hüffner, Komusiewicz, and Nichterlein. <em>"Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes."</em></p>

CC BY-SA 3.0
2015-05-11T09:49:35.627Z
2015-05-11T09:55:30.780Z
2015-05-11T09:55:30.780Z
John K.
<p>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, <a href="http://www.mathcove.net/petersen/lessons/get-lesson?les=30">http://www.mathcove.net/petersen/lessons/get-lesson?les=30</a> ). Hence you could call your graph class co-complete split graphs.</p>

CC BY-SA 3.0
2015-05-07T09:01:02.680Z
Thanks, Bart.  It doesn't exactly roll off the tongue, but I guess it'll have to do.
John K.
CC BY-SA 3.0
2015-05-13T16:17:12.943Z
What about _independent split graph_?  Or would that be likely to be confused with something else?
John K.
CC BY-SA 3.0
2015-05-06T08:24:56.970Z
2015-05-06T08:24:56.970Z
Bart Jansen
<p>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} .$$</p>

<p>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.</p>

<p>Does this (very simple) graph class have a name?  I was unable to find the graph class on&nbsp;<a href="http://www.graphclasses.org/" rel="noreferrer">ISGCI</a>, and the papers I know on the topic (e.g. <a href="http://jgaa.info/getPaper?id=337" rel="noreferrer">Editing Simple Graphs</a> and <a href="http://link.springer.com/chapter/10.1007/978-3-662-44465-8_40" rel="noreferrer">On the clique editing problem</a>) do not refer to the class by a name.</p>

<p>Here is a figure of such a graph:</p>

<p><img src="https://i.sstatic.net/DviE9.png" alt="cluster-split graph"></p>

CC BY-SA 3.0
2015-05-05T18:12:09.787Z
Unfortunately "split cluster graphs" seems to be in use for a different concept (graphs in which each connected component is split).
David Eppstein
<reference-request><graph-theory><graph-classes>
Name the graph class: Disjoint union of a clique and an independent set
John K.
# Name the graph class: Disjoint union of a clique and an independent set

(Asked by: username_0 on 2015-05-05)

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](http://www.graphclasses.org/), and the papers I know on the topic (e.g. [Editing Simple Graphs](http://jgaa.info/getPaper?id=337) and [On the clique editing problem](http://link.springer.com/chapter/10.1007/978-3-662-44465-8_40)) do not refer to the class by a name.

Here is a figure of such a graph:

![cluster-split graph](https://i.sstatic.net/DviE9.png)

**Tags:** reference-request, graph-theory, graph-classes

> **Comments:**
> **username_1**: Unfortunately "split cluster graphs" seems to be in use for a different concept (graphs in which each connected component is split).  

---

## 2 answers

### Answer by username_2 on 2015-05-06. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks, Bart.  It doesn't exactly roll off the tongue, but I guess it'll have to do.  
> **username_0**: What about _independent split graph_?  Or would that be likely to be confused with something else?  

---

### Answer by username_0 on 2015-05-11. Score: 8

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


---

