Primary minimal dom-path length conjecture for linear Jaco graphs

From papers

Let Jn(x)J_n(x) be a linear Jaco graph of order n1n\geq1. A diam-path is a path of diameter length, and let PdP_d be a primary minimal dom-path, meaning a minimal path from v1v_1 to vnv_n whose γ\gamma-set is also a γ\gamma-set of Jn(x)J_n(x). Primary minimal dom-path conjecture. The length of a diam-path and the primary minimal dom-path satisfy

Pddiam(Jn(x))1.|P_d|-|\operatorname{diam}(J_n(x))|\leq1.

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

Open

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 Pddiam(Jn(x))1|P_d|-|\operatorname{diam}(J_n(x))|\leq1. 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

Counterexample

Consider J33J_{33}, and write φ=(1+5)/2\varphi=(1+\sqrt5)/2. For i<ji<j, the Jaco adjacency rule is

vivjE(J33)jU(i),U(i)=2ii+1φ2.v_i v_j\in E(J_{33}) \quad\Longleftrightarrow\quad j\le U(i), \qquad U(i)=2i-\left\lfloor\frac{i+1}{\varphi^2}\right\rfloor.

The four closed neighborhoods

N[v1]={v1,v2},N[v4]={v3,,v7},N[v12]={v8,,v20},N[v33]={v21,,v33}\begin{aligned} N[v_1]&=\{v_1,v_2\},\\ N[v_4]&=\{v_3,\ldots,v_7\},\\ N[v_{12}]&=\{v_8,\ldots,v_{20}\},\\ N[v_{33}]&=\{v_{21},\ldots,v_{33}\} \end{aligned}

are pairwise disjoint. Therefore γ(J33)4\gamma(J_{33})\ge4. Conversely,

D={v2,v7,v20,v33}D=\{v_2,v_7,v_{20},v_{33}\}

dominates J33J_{33}, so γ(J33)=4\gamma(J_{33})=4.

Since UU is increasing, the successive maximal forward reaches from v1v_1 have indices

1, 2, 3, 5, 8, 13, 21, 34.1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34.

Thus d(v1,v33)=7d(v_1,v_{33})=7. Starting from any larger vertex reaches at least as far, so every vertex pair has distance at most 77, and hence

diam(J33)=7.\operatorname{diam}(J_{33})=7.

Every primary minimal dom-path PP must satisfy

γ(P)=γ(J33)=4.\gamma(P)=\gamma(J_{33})=4.

Because γ(P)=V(P)/3\gamma(P)=\lceil |V(P)|/3\rceil, such a path has at least ten vertices and therefore at least nine edges. Equality is attained by

P=(v1,v2,v3,v4,v7,v11,v12,v20,v32,v33).P=(v_1,v_2,v_3,v_4,v_7,v_{11},v_{12},v_{20},v_{32},v_{33}).

Its consecutive vertices are adjacent, and DD occupies path positions 2,5,8,102,5,8,10. Thus DD is a minimum dominating set of both PP and J33J_{33}, so PP is a primary minimal dom-path of length 99.

Consequently,

Pddiam(J33)=97=2>1,|P_d|-\operatorname{diam}(J_{33})=9-7=2>1,

contradicting the conjectured bound.

0 endorsements
Shivam Patel ·