Paired-domination of cartesian products of graphs - Brešar, Boštjan,; Henning, Michael A.,; Rall, Douglas F., (Utilitas Mathematica, 2007)
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).