Characterization of graphs with equal domination and covering number Original Research Article

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 γ(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 γ(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 γ(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)2] 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 γ(G) = [n(G)2].