Existence conjecture for perfect distance-dominating sets with path components
Existence conjecture for perfect distance-dominating sets with path components
Let be the -dimensional lattice graph, and let denote the path on vertices. For a finite graph , a -PDDS in is a perfect distance-dominating set whose components are all isomorphic to . The Cartesian product of graphs is denoted by .
Existence conjecture. Let be a finite path or a Cartesian product of two finite paths. Then a -PDDS in exists if and only if at least one of the following holds: (i) , , and for some ; (ii) , , and for some ; (iii) , , and for some ; (iv) , for some , and ; or (v) , , and .
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 and do not yet have enough evidence for the general case; the listed cases are proposed because they are strongly believed when 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
Sign in to submit a solution.
No solutions have been posted yet.