Paired-domination of cartesian products of graphs

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 ρ₃(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) ρ₃(H),γ_pr(H)ρ₃(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).