تسجيل الدخول

تسجيل

Clique Covering Number

المؤلف:  West, D. B

المصدر:  Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall,

الجزء والصفحة:  p. 226

4-3-2022

2115

Clique Covering Number

The clique covering number  of a graph  is the minimum number of cliques in  needed to cover the vertex set of . Since  involves the minimum number of cliques, only maximal cliques need be considered (since non-maximal cliques could not yield a clique cover of smaller size).

The clique covering number is also given by

where  is the chromatic number of a graph  and  is the graph complement of .

The clique covering number of some classes of graph are given by

 

graph
complete -partite graph  with
complete graph	1
cycle graph	{n/2 for n even; (n+1)/2 for n odd" src="https://mathworld.wolfram.com/images/equations/CliqueCoveringNumber/Inline18.svg" style="height:68px; width:225px" />

---

REFERENCES

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 226, 2000.