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.


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.

  • 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 '14 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 '14 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$ Feb 18 '14 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 '14 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$ Feb 19 '14 at 11:06

I believe the most standard term is complete multipartite graph.

  • $\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 '14 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$ Feb 18 '14 at 13:06
  • 4
    $\begingroup$ The notation applies only for fixed k. $\endgroup$ Feb 18 '14 at 15:42
  • 1
    $\begingroup$ @TobiasMüller: Are you commenting on the answer or on the previous comment? $\endgroup$ Feb 19 '14 at 0:05
  • $\begingroup$ @SergeGaspers My comment is about the notation $K_{s,t}$, $K_{a_1,a_2,\ldots,a_k}$. $\endgroup$ Feb 19 '14 at 10:57

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.

  • $\begingroup$ Sorry, what's P_3? $\endgroup$
    – dspyz
    Feb 20 '14 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 '14 at 0:21

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.