Download PDF - Paired-dominationAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Paired-domination

Authors 1, 2

Affiliations

  1. Dalhousie University, Halifax, Canada, B3H 3J5
  2. Saint Mary's University, Halifax, Canada, B3H 3C3

Abstract

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

ENG
domination, paired-domination, matching

Bibliography

  1. T.W. Haynes and P.J. Slater, Paired-domination in graphs, submitted for publication.
  2. T.W. Haynes and P.J. Slater, Paired-domination and the paired-domatic number, Congressus Numerantium 109 (1995) 65-72.
Discussiones Mathematicae Graph Theory
1998/18/1
Export to PBN, Opens in new tab
Pages:
63-72
Main language of publication
English
Received
1997-02-18
Accepted
1997-09-12
Published
1998

DOI: 10.7151/dmgt.1063

Exact and natural sciences