Paired-domination of cartesian products of graphs

Boštjan Brešar, Michael A. Henning, Douglas F. Rall

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


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 languageEnglish
Pages (from-to)255-265
Number of pages11
JournalUtilitas Mathematica
Publication statusPublished - 2007
Externally publishedYes


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

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


Dive into the research topics of 'Paired-domination of cartesian products of graphs'. Together they form a unique fingerprint.

Cite this