Characterization of graphs with equal domination and matching number

Abstract

Let G be a simple undirected graph. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. A set M of edges of G is called independent, or a matching, if no two edges of M are incident in G. The domination number γ(G) is the minimum order of a dominating set, and the matching number α₀(G) is the maximum size of a matching of G. If G has no isolated vertices, then the inequality γ(G) ≤ α₀(G) holds. In this paper we characterize the graphs G without isolated vertices and with γ(G) = α₀(G). In order to achieve the characterization we make use of the Gallai-Edmonds Structure Theorem.