An introduction to proper-coupled-domination in graphs

ABSTRACT

In this paper we introduce the proper-coupled-domination problem. Specifically, assume that we have (disjoint) subsets S1, S2, ..., St of the vertex set V(G) of graph G. One seeks to find the minimum cardinality of a dominating set D with the property that D ∩ Si ≠ &phis; implies that Si ⊆ D for 1 ≤ i ≤ t. We focus, in particular, on a coupled-domination parameter for which each Si has cardinality at most two.

REFERENCES

• 1: S. Fitzpatrick and B. Hartnell, Paired-domination, Discuss. Math. - Graph Theory, 18, 1998, 63--72.
• 2: T. W. Haynes and P. J. Slater, Paired-domination and the paired-domatic number, Cong. Num. 109, 1995, 67--72.
• 3: T. W. Haynes and P. J. Slater, Paired-domination in Graphs, Networks 32, 1998, 199--206.
• 4: T. W. Haynes, K. Proffitt and P. J. Slater, Paired-domination in grid graphs, Cong. Num. 150, 2001, 161--172.
• 5: Suk J. Seo and Peter J. Slater, Colored-Domination in Graphs, Congressus Numerantium 167 (2004), pp 149--159.
• 6: P. J. Slater, Colored problems in graphs, to appear.
• 7: P. J. Slater, An Introduction to Colored-independence in Graphs, Congressus Numerantium (2005), to appear.
• 8: P. J. Slater, Enclaveless sets and MK-systems, J. Res. Nat. Bur. Standards, 82, 1977, 197--202.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Theory

Keywords:
colored problems, domination, proper colored domination