The strong-product infinity conjecture for distance packing domination

From papers

Let GG and HH be graphs, and let dd and pp be integers. The dd-distance pp-packing domination number γdp(G)\gamma_d^p(G) is the cardinality of a smallest set of vertices that is both a dd-distance dominating set and a pp-packing; if no such set exists, it is defined to be infinity. The strong product GHG\boxtimes H has vertex set V(G)×V(H)V(G)\times V(H), with adjacency inherited from adjacency in either factor or both factors.

Strong-product infinity conjecture. If

γdp(G)=,\gamma_d^p(G)=\infty,

then

γdp(GH)=\gamma_d^p(G\boxtimes H)=\infty

for every graph HH.

The conjecture asks whether the nonexistence of a dd-distance pp-packing dominating set in one factor necessarily persists after taking its strong product with any graph. The paper establishes the upper bound γdp(GH)γdp(G)γdp(H)\gamma_d^p(G\boxtimes H)\leq \gamma_d^p(G)\gamma_d^p(H) when the relevant quantities are finite, but the converse implication concerning infinity is left as a conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Csilla Bujtás, Vesna Iršič Chenoweth, Sandi Klavžar and Gang Zhang, “On d-distance p-packing domination number in strong products”, arXiv:2510.02749 (2025).

Solutions 0

No solutions have been posted yet.