×

Characterization of graphs with equal domination and matching number. (English) Zbl 0940.05058

Summary: 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 \(\gamma(G)\) is the minimum order of a dominating set, and the matching number \(\alpha_0(G)\) is the maximum size of a matching of \(G\). If \(G\) has no isolated vertices, then the inequality \(\gamma(G)\leq \alpha_0(G)\) holds. In this paper we characterize the graphs \(G\) without isolated vertices and with \(\gamma(G)= \alpha_0(G)\). In order to achieve the characterization we make use of the Gallai-Edmonds structure theorem.

MSC:

05C75 Structural characterization of families of graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite