## Abstract

The most famous open problem involving domination in graphs is Vizing's conjecture which states the domination number of the Cartesian product of any two graphs is at least as large as the product of their domination numbers. In this paper, we investigate a similar problem for paired-domination. A paired-dominating set of a graph G is a set S of vertices of G such that every vertex is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number γ_{pr}(G) of G is the minimum cardinality of a paired-dominating set. A 3-packing in G is a set of vertices of G that are pairwise at distance greater than 3 apart in G, and the 3-packing number ρ_{3}(G) of G is the maximum cardinality of a 3-packing in G. We prove that for any graphs G and H without isolated vertices, γ_{pr}(G□H) ≥ max{γ_{pr}(G) ρ_{3}(H),γ_{pr}(H)ρ_{3}(G)} where G□H denotes the Cartesian product of G and H. We then establish that the product of the paired-domination numbers of any nontrivial tree G and any graph H without isolated vertices is at most twice the paired-domination number of their Cartesian product; that is γ_{pr}(G)γ_{pr}(H) ≤ 2_{γpr}(G□H).

Original language | English |
---|---|

Pages (from-to) | 255-265 |

Number of pages | 11 |

Journal | Utilitas Mathematica |

Volume | 73 |

Publication status | Published - 2007 |

Externally published | Yes |

## Keywords

- 3-packing
- Graph products
- Paired-domination
- Vizing's conjecture

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics