On a conjecture on the d-distance p-packing dominating number of strong product graphs: Counterexamples and partial results
Demaret Hugo (GREYC, Caen)Given a graph G, a d-distance dominating set of G is a subset of vertices D ⊂V (G) such that for any v ∈ V(G), there exists x ∈ D such that d_G(v, x) ≤ d. A p-packing of G is a subset of vertices P ⊂V(G) such that d_G(u, v) ≥ p + 1 for every u, v ∈ P. A subset of vertices is a d-distance p-packing dominating set if it is both a d-distance dominating set of G and a p-packing in G. The d-distance p-packing number gdp(G) of a graph G is the minimum cardinality of a smallest d-distance p-packing dominating set of G. If no such set exists, we set gdp(G) = ∞. Recently, Bujtas, Chenoweth, Klavzar, and Zhang conjectured that if gdp(G) = ∞ then, for any graph H, gdp(G ⊠ H) = ∞.
We prove that when G is a cycle with p ≥ 3d/2, the conjecture holds, and find an infinite family of counterexamples whenever p < 3d/2 and with G a cycle of order 4d + 3.
This is a joint work with Paul Dorbec.