What is the graph $K^c_m$?

120 Views Asked by At

The book "Graph Theory with applications" by J.A. Bondy and U.S.R. Murty, which is available here. The Theorem $4.6$ of this book says that:

If $G$ is a non-Hamiltonian simple graph with $n≥3$ vertices, then $G$ is degree-majorised by some $C_{m,n}:=K_m \vee (K^c_m+K_{n−2m})$

What does $K^c_m$ mean?

Thanks in advance.

1

There are 1 best solutions below

0
On

As per Chapter 1 Exercise 1.2.11, $K_m^c$ denotes the complement of the complete graph $K_m$.

That is, the graph composed of $m$ isolated vertices.