ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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, n≥2n\geq 2, and H=PkH=P_k for some k≥1k\geq 1; (ii) t≥1t\geq 1, n=2n=2, and H=PkH=P_k for some k≥1k\geq 1; (iii) t≥1t\geq 1, n=2n=2, and H=P2□PkH=P_2\square P_k for some k≥2k\geq 2; (iv) t=1t=1, n=3r+2n=3r+2 for some r≥0r\geq 0, and H=P2□P2H=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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.