Paired-domination

• Autorzy: S. Fitzpatrick , B. Hartnell
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

domination; paired-domination; matching

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1998
• Tom: 18
• Numer: 1
• Strony: 63-72

Daty

wydano

1998

otrzymano

1997-02-18

poprawiono

1997-09-12

Twórcy

autor

S. Fitzpatrick

• Dalhousie University, Halifax, Canada, B3H 3J5

autor

B. Hartnell

• Saint Mary's University, Halifax, Canada, B3H 3C3

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1063