
doi: 10.7151/dmgt.1063
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.
paired-dominating set, matching, Structural characterization of families of graphs, dominating set
paired-dominating set, matching, Structural characterization of families of graphs, dominating set
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 22 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
