Primary minimal dom-path length conjecture for linear Jaco graphs
Primary minimal dom-path length conjecture for linear Jaco graphs
Let be a linear Jaco graph of order . A diam-path is a path of diameter length, and let be a primary minimal dom-path, meaning a minimal path from to whose -set is also a -set of . Primary minimal dom-path conjecture. The length of a diam-path and the primary minimal dom-path satisfy
The surrounding discussion establishes the existence of a primary minimal dom-path and compares it with diameter paths in examples; the inequality itself is presented conjecturally and is not resolved in the supplied source.
Progress summary
The conjecture remains open: a 2025 paper records it but neither proves nor disproves it.
The conjecture asserts that a primary minimal dom-path is at most one edge longer than a diameter path, namely . The supplied source records examples and an existence result for suitable dom-paths, but does not settle this inequality.
2025 preprint
The paper “Integer sequences with conjectured relation with certain graph parameters of the family of linear Jaco graphs” states the inequality as Conjecture 2.9 and explicitly leaves its proof or disproof to future work. The search found no corroborated proof, counterexample, or claimed resolution for this specific conjecture.
Current status (as of August 2026): The inequality remains an open conjecture, with no corroborated proof or disproof in the supplied sources.
Sources
Sources & referencesView supporting material
Primary source
Johan Kok, “Integer sequences with conjectured relation with certain graph parameters of the family of linear Jaco graphs”, arXiv:2507.16500 (2025).
Solutions 1
Sign in to submit a solution.
Consider , and write . For , the Jaco adjacency rule is
The four closed neighborhoods
are pairwise disjoint. Therefore . Conversely,
dominates , so .
Since is increasing, the successive maximal forward reaches from have indices
Thus . Starting from any larger vertex reaches at least as far, so every vertex pair has distance at most , and hence
Every primary minimal dom-path must satisfy
Because , such a path has at least ten vertices and therefore at least nine edges. Equality is attained by
Its consecutive vertices are adjacent, and occupies path positions . Thus is a minimum dominating set of both and , so is a primary minimal dom-path of length .
Consequently,
contradicting the conjectured bound.