Discrete Mathematics & Theoretical Computer Science, Vol 10, No 1 (2008)

Font Size:  Small  Medium  Large

Total domination in K5- and K6-covered graphs

Odile Favaron, Hosein Karami, Seyed Mahmoud Sheikholeslami


A graph G is Kr-covered if each vertex of G is contained in a Kr-clique. Let γt(G) denote the total domination number of G. It has been conjectured that every Kr-covered graph of order n with no Kr-component satisfies γt(G) ≤ 2n/(r+1). We prove that this conjecture is true for r=5 and 6.

Full Text: PDF PostScript