Characterization of graphs with equal domination and covering number

✍ Scribed by Bert Randerath; Lutz Volkmann

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 592 KB
• Volume: 191
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00103-4

✦ Synopsis

Let G be a simple graph of order n(G). A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D, and D is a covering if every edge of G has at least one end in D. The domination number 7(G) is the minimum order of a dominating set, and the covering number/~(G) is the minimum order of a covering set in G. In 1981, Laskar and Walikar raised the question of characterizing those connected graphs for which 7(G) =/~(G). It is the purpose of this paper to give a complete solution of this problem. This solution shows that the recognition problem, whether a connected graph G has the property 7(G)=/~(G), is solvable in polynomial time. As an application of our main results we determine all connected extremal graphs in the well-known inequality ),(G)~< [n(G)/2J of Ore (1962), which extends considerable a result of Payan and Xuong from 1982. With a completely different method, independently around the same time, Cockayne, Haynes and Hedetniemi also characterized the connected graphs G with 7(G) = Ln(G)/2j. @