Primary minimal dom-path length conjecture for linear Jaco graphs

Let $J_n(x)$ be a linear Jaco graph of order $n\geq1$ . A diam-path is a path of diameter length, and let $P_d$ be a primary minimal dom-path, meaning a minimal path from $v_1$ to $v_n$ whose $\gamma$ -set is also a $\gamma$ -set of $J_n(x)$ . Primary minimal dom-path conjecture. The length of a diam-path and the primary minimal dom-path satisfy

|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.

References

Primary source

Johan Kok, “Integer sequences with conjectured relation with certain graph parameters of the family of linear Jaco graphs”, arXiv:2507.16500 (2025).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

An unverified construction claims a counterexample in a 33-vertex graph, so the conjecture is challenged but not settled.

Johan Kok posed the conjecture in 2025: a primary minimal dom-path should exceed a diameter path by at most one edge. The source presents it as unresolved and supplies only experimental evidence.

Known results

In $J_8(x)$ , the example has diameter-path length $4$ and primary minimal dom-path length $5$ .
In $J_{15}(x)$ , both lengths are $6$ .
The source records existence of primary minimal dom-paths, but not the conjectured bound.

Posted attempt (date unavailable)

A reader claims that $J_{33}$ has diameter $7$ , while every primary minimal dom-path has length at least $9$ , and gives one of length $9$ , yielding $|P_d|-|\operatorname{diam}(J_{33})|=2$ . This would disprove the conjecture, but the calculation has not been independently verified.

Current status (as of August 2026): The conjecture has no published proof or corroborated disproof; an unverified $J_{33}$ counterexample claim is the only reported challenge.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

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

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

\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 $\gamma(J_{33})\ge4$ . Conversely,

D=\{v_2,v_7,v_{20},v_{33}\}

dominates $J_{33}$ , so $\gamma(J_{33})=4$ .

Since $U$ is increasing, the successive maximal forward reaches from $v_1$ have indices

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

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

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

Every primary minimal dom-path $P$ must satisfy

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

Because $\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=(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 $D$ occupies path positions $2,5,8,10$ . Thus $D$ is a minimum dominating set of both $P$ and $J_{33}$ , so $P$ is a primary minimal dom-path of length $9$ .

Consequently,

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

contradicting the conjectured bound.