Existence conjecture for perfect distance-dominating sets with path components

From papers

Let Λn\Lambda_n be the nn-dimensional lattice graph, and let PkP_k denote the path on kk vertices. For a finite graph HH, a tt-PDDS[H][H] in Λn\Lambda_n is a perfect distance-dominating set whose components are all isomorphic to HH. The Cartesian product of graphs is denoted by \square.

Existence conjecture. Let HH be a finite path or a Cartesian product of two finite paths. Then a tt-PDDS[H][H] in Λn\Lambda_n exists if and only if at least one of the following holds: (i) t=1t=1, n2n\geq 2, and H=PkH=P_k for some k1k\geq 1; (ii) t1t\geq 1, n=2n=2, and H=PkH=P_k for some k1k\geq 1; (iii) t1t\geq 1, n=2n=2, and H=P2PkH=P_2\square P_k for some k2k\geq 2; (iv) t=1t=1, n=3r+2n=3r+2 for some r0r\geq 0, and H=P2P2H=P_2\square P_2; or (v) t=2t=2, n=3n=3, and H=P2H=P_2.

This conjecture seeks to characterize the cases in which perfect distance-dominating sets with components that are paths or products of two paths exist. The source states that the authors can characterize such graphs only for Λ2\Lambda_2 and do not yet have enough evidence for the general case; the listed cases are proposed because they are strongly believed when HH has the specified form.

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

Carlos Araujo, Italo J. Dejter and Peter Horak, “A Generalization of Lee Codes”, arXiv:1210.5863 (2013).

Solutions 0

No solutions have been posted yet.