<p>How about this: 
Call your graphs simply <em>$(K_1 + K_2)$-free graphs</em>, where $K_n$ 
is the complete graph with $n$ vertices, + stands for disjoint union, and $H$-free means without $H$ as an induced subgraph.  </p>

CC BY-SA 3.0
2014-02-18T02:56:12.073Z
I don't think that means the same thing.  For instance, the four-vertex graph which is simply 3 edges joined in a line is not a complete k-partite graph, but it is (K_1+K_2)-free
dspyz
CC BY-SA 3.0
2014-02-18T03:00:24.737Z
I edited my question to clarify.  By "is a set of disjoint cliques" I meant "each connected component is a clique"
dspyz
CC BY-SA 3.0
2014-02-18T14:00:22.640Z
@dspyz your 4-vertex example is NOT (K1+K2)-free. Note: complete multipartite graphs and (K1+K2)-free graphs coincide.
Tobias Müller
CC BY-SA 3.0
2014-02-18T22:15:15.987Z
Ok, I see that every complete multipartite graph is (K1+K2) free and also that my example was wrong, but it's still not obvious to me that the converse is true.  Do you have a proof?
dspyz
CC BY-SA 3.0
2014-02-19T11:06:40.947Z
@dspyz your observation is a proof: complete multipartite = each connected component is a clique = co-(K1+K2)-free = P3-free = cluster graphs (cf. Bangye's answer).
Tobias Müller
CC BY-SA 3.0
2014-02-20T16:45:01.930Z
Sorry, which observation is a proof?  How do you know every K1+K2-free graph is complete multipartite?
dspyz
CC BY-SA 3.0
2014-02-20T16:59:19.637Z
Ok, I see why now.  If the graph is not complete multipartite, than there exist two nodes, X and Y, which have an edge in the original graph and also a path in the complement graph (I'll call it a "non-path").  Pick the shortest-such non-path between X and Y.  Now pick any intermediate node N in the non-path and look at its neighbors on either side A and B.  Either A and B are connected by an edge in which case N + AB is K1+K2.  If they're not, then we can craft a shorter non-path between X and Y by eliminating N from the path and using the direct non-connection between A and B.
dspyz
CC BY-SA 3.0
2014-02-17T22:26:11.583Z
2014-02-18T18:25:28.613Z
2014-02-18T18:25:28.613Z
user13136
<p>I believe the most standard term is <a href="http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Independence">complete multipartite graph</a>.</p>

CC BY-SA 3.0
2014-02-18T12:23:14.953Z
Yes, I think you see this often. This generalizes the complete bipartite graph $K_{s,t}$ used by some authors.
Juho
CC BY-SA 3.0
2014-02-18T13:06:39.773Z
Moreover, I have seen the notation $K_{a_1,a_2,\dots,a_k}$ used, for a complete multipartite graph with partitions of sizes $a_1, a_2,\dots, a_k$.
András Salamon
CC BY-SA 3.0
2014-02-18T15:42:21.280Z
The notation applies only for fixed k.
Tobias Müller
CC BY-SA 3.0
2014-02-19T00:05:40.703Z
@TobiasMüller: Are you commenting on the answer or on the previous comment?
Serge Gaspers
CC BY-SA 3.0
2014-02-19T10:57:15.417Z
@SergeGaspers My comment is about the notation $K_{s,t}$, $K_{a_1,a_2,\ldots,a_k}$.
Tobias Müller
CC BY-SA 3.0
2014-02-19T14:34:07.533Z
@TobiasMüller: Ok, thanks for clearing that up.
Serge Gaspers
CC BY-SA 3.0
2014-02-18T12:11:08.907Z
2014-02-18T12:11:08.907Z
Serge Gaspers
<p>A cluster graph consists of disjoint maximal cliques, i.e., each connected component is a clique. Your complete k-partite graph for non-fixed k is the complement of a cluster graph. Also, a graph is cluster graph iff it is "induced $P_3$-free". Modifying a graph into a cluster graph with minimum number of edge insertions and deletions has been extensively studied in the area of parameterized algorithms. You can google "cluster graph editing" or "correlation clustering" to find them.</p>

CC BY-SA 3.0
2014-02-20T16:49:35.200Z
Sorry, what's P_3?
dspyz
CC BY-SA 3.0
2014-02-21T00:21:26.770Z
$P_3$ is a path of three nodes. Three nodes with exactly two edge is an induced $P_3$. These are common notation in graph theory.
Bangye
CC BY-SA 3.0
2014-02-18T17:02:28.900Z
2014-02-18T17:02:28.900Z
Bangye
<p>Is there a better term for "complete k-partite graph" in the case where k is not fixed?  If I say "complete k-partite graph", people tend to assume "for some particular k".</p>

<p>In other words, what's a term for any graph for whom each connected component in the complement graph is a clique?</p>

<p>I asked this before, but it was as part of another question, so it was ignored.</p>

<graph-theory><terminology><clique>
Terminology for complete k-partite graph where k is not fixed
dspyz
# Terminology for complete k-partite graph where k is not fixed

(Asked by: username_0 on 2014-02-17)

Is there a better term for "complete k-partite graph" in the case where k is not fixed? If I say "complete k-partite graph", people tend to assume "for some particular k".

In other words, what's a term for any graph for whom each connected component in the complement graph is a clique?

I asked this before, but it was as part of another question, so it was ignored.

**Tags:** graph-theory, terminology, clique


---

## 3 answers

### Answer by username_1 on 2014-02-17. Score: 8 | Accepted answer

How about this:
Call your graphs simply *$(K\_1 + K\_2)$-free graphs*, where $K\_n$
is the complete graph with $n$ vertices, + stands for disjoint union, and $H$-free means without $H$ as an induced subgraph.

> **Comments:**
> **username_0**: I don't think that means the same thing.  For instance, the four-vertex graph which is simply 3 edges joined in a line is not a complete k-partite graph, but it is (K_1+K_2)-free  
> **username_0**: I edited my question to clarify.  By "is a set of disjoint cliques" I meant "each connected component is a clique"  
> **username_2**: @username_0 your 4-vertex example is NOT (K1+K2)-free. Note: complete multipartite graphs and (K1+K2)-free graphs coincide.  
> **username_0**: Ok, I see that every complete multipartite graph is (K1+K2) free and also that my example was wrong, but it's still not obvious to me that the converse is true.  Do you have a proof?  
> **username_2**: @username_0 your observation is a proof: complete multipartite = each connected component is a clique = co-(K1+K2)-free = P3-free = cluster graphs (cf. username_6's answer).  
> **username_0**: Sorry, which observation is a proof?  How do you know every K1+K2-free graph is complete multipartite?  
> **username_0**: Ok, I see why now.  If the graph is not complete multipartite, than there exist two nodes, X and Y, which have an edge in the original graph and also a path in the complement graph (I'll call it a "non-path").  Pick the shortest-such non-path between X and Y.  Now pick any intermediate node N in the non-path and look at its neighbors on either side A and B.  Either A and B are connected by an edge in which case N + AB is K1+K2.  If they're not, then we can craft a shorter non-path between X and Y by eliminating N from the path and using the direct non-connection between A and B.  

---

### Answer by username_3 on 2014-02-18. Score: 9

I believe the most standard term is [complete multipartite graph](http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Independence).

> **Comments:**
> **username_4**: Yes, I think you see this often. This generalizes the complete bipartite graph $K_{s,t}$ used by some authors.  
> **username_5**: Moreover, I have seen the notation $K_{a_1,a_2,\dots,a_k}$ used, for a complete multipartite graph with partitions of sizes $a_1, a_2,\dots, a_k$.  
> **username_2**: The notation applies only for fixed k.  
> **username_3**: @TobiasMüller: Are you commenting on the answer or on the previous comment?  
> **username_2**: @SergeGaspers My comment is about the notation $K_{s,t}$, $K_{a_1,a_2,\ldots,a_k}$.  
> **username_3**: @TobiasMüller: Ok, thanks for clearing that up.  

---

### Answer by username_6 on 2014-02-18. Score: 1

A cluster graph consists of disjoint maximal cliques, i.e., each connected component is a clique. Your complete k-partite graph for non-fixed k is the complement of a cluster graph. Also, a graph is cluster graph iff it is "induced $P\_3$-free". Modifying a graph into a cluster graph with minimum number of edge insertions and deletions has been extensively studied in the area of parameterized algorithms. You can google "cluster graph editing" or "correlation clustering" to find them.

> **Comments:**
> **username_0**: Sorry, what's P_3?  
> **username_6**: $P_3$ is a path of three nodes. Three nodes with exactly two edge is an induced $P_3$. These are common notation in graph theory.  

---

