Paired-domination

It is known that a dominating set \(S\) of vertices of a graph \(G\) is a set such that every vertex of \(G\) is either in \(S\) or adjacent to at least one member of \(S\). A paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. The size of a minimum paired-dominating set be denoted by \(\gamma_p\). This set is also called a \(\gamma_p\)-set. In the present paper connected graphs \(G\) with no vertices of degree one are considered which have some maximal matching whose end vertices form a \(\gamma_p\)-set. The set of all graphs \(G\) of this type which have girth at least seven be denoted by \({\mathfrak G}\). In Chapter 2 properties of the graphs \(G\in{\mathfrak G}\) are proved, for example: (1) the girth of \(G\) is at most nine (Corollary 1), or (2) \(G\) does not contain a 7-cycle (Lemma 3), or (3) no edge of a maximal matching in \(G\) lies on an 8-cycle (Lemma 4). In Chapter 3 an infinite family \({\mathfrak F}\) is defined. It is the set of those graphs \(H\) which can be obtained in a given way from three nonempty sets of parallel edges by connecting vertices with a path of length two. Also the graphs \(H\in {\mathfrak F}\) have no vertices of degree one, they have girth at least eight, and the so-called ``associated matching of any \(H\) is a maximal matching. The main result of the paper follows from Theorems 1 and 2: The graphs in \({\mathfrak G}\) are precisely the graphs in \({\mathfrak F}\). This result means that the number of matched pairs of a minimum dominating set of \(G\) equals the size of some maximal matching in the graph.

Recommendations

Cited in

(26)

This page was built for publication: Paired-domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4222381)