ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Graph Theory 18(1) (1998) 63-72DOI: 10.7151/dmgt.1063
Dalhousie University, Halifax, Canada, B3H 3J5
Saint Mary's University, Halifax, Canada, B3H 3C3
We are interested in dominating sets (of vertices) with the additional property that
the vertices in the dominating set can be paired or matched via existing edges in the
graph. This could model the situation of guards or police where each has a partner or
backup. This paper will focus on those graphs in which the number of matched pairs of a
minimum dominating set of this type equals the size of some maximal matching in the graph.
In particular, we characterize the leafless graphs of girth seven or more of this type.
Keywords: domination, paired-domination, matching.
1991 Mathematics Subject Classification: 05C75.
Received 18 February 1997
Revised 12 September 1997