0
$\begingroup$

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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 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 $\endgroup$
    – dspyz
    Feb 18, 2014 at 2:56
  • $\begingroup$ I edited my question to clarify. By "is a set of disjoint cliques" I meant "each connected component is a clique" $\endgroup$
    – dspyz
    Feb 18, 2014 at 3:00
  • 6
    $\begingroup$ @dspyz your 4-vertex example is NOT (K1+K2)-free. Note: complete multipartite graphs and (K1+K2)-free graphs coincide. $\endgroup$
    – Tobias Müller
    Feb 18, 2014 at 14:00
  • $\begingroup$ 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? $\endgroup$
    – dspyz
    Feb 18, 2014 at 22:15
  • $\begingroup$ @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). $\endgroup$
    – Tobias Müller
    Feb 19, 2014 at 11:06
9
$\begingroup$

I believe the most standard term is complete multipartite graph.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, I think you see this often. This generalizes the complete bipartite graph $K_{s,t}$ used by some authors. $\endgroup$
    – Juho
    Feb 18, 2014 at 12:23
  • $\begingroup$ 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$. $\endgroup$
    – András Salamon
    Feb 18, 2014 at 13:06
  • 4
    $\begingroup$ The notation applies only for fixed k. $\endgroup$
    – Tobias Müller
    Feb 18, 2014 at 15:42
  • 1
    $\begingroup$ @TobiasMüller: Are you commenting on the answer or on the previous comment? $\endgroup$
    – Serge Gaspers
    Feb 19, 2014 at 0:05
  • $\begingroup$ @SergeGaspers My comment is about the notation $K_{s,t}$, $K_{a_1,a_2,\ldots,a_k}$. $\endgroup$
    – Tobias Müller
    Feb 19, 2014 at 10:57
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, what's P_3? $\endgroup$
    – dspyz
    Feb 20, 2014 at 16:49
  • 1
    $\begingroup$ $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. $\endgroup$
    – Bangye
    Feb 21, 2014 at 0:21

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.