Let J_∞(x) be the infinite linear Jaco graph, and let X be a gamma-set, that is, a minimum dominating set. The vertex subscripts in the displayed set are 1,2,7,20,54,…. A sequence is p-graphical for a graph family F when it gives the values of a graph parameter p on the members of F. Euler-exponential gamma-set conjecture. The vertex subscripts of a gamma-set X=v_1cupv_2,v_7,v_20,v_54,… of J_∞(x) are given by sequence A000149: a(t)=lfloor e^t rfloor,qquad t=0,1,2,…, where e approx2.71828 is Euler's number. Moreover, sequence A000149 is p-graphical for the parameter consisting of the subscripts of vertices in some gamma-set of G, over F=G:G=J_n(x), n=1,2,3,…. The source offers a sequence-based conjecture for the domination structure but gives no proof or resolution.

Euler-exponential gamma-set conjecture for the infinite linear Jaco graph

About 1 year old · traced to 2025

Let $J_\infty(x)$ be the infinite linear Jaco graph, and let $X$ be a $\gamma$ -set, that is, a minimum dominating set. The vertex subscripts in the displayed set are $1,2,7,20,54,\dots$ . A sequence is $p$ -graphical for a graph family $\mathcal{F}$ when it gives the values of a graph parameter $p$ on the members of $\mathcal{F}$ . Euler-exponential gamma-set conjecture. The vertex subscripts of a $\gamma$ -set

X=\{v_1\}\cup\{v_2,v_7,v_{20},v_{54},\dots\}

of $J_\infty(x)$ are given by sequence A000149:

a(t)=\lfloor e^t\rfloor,\qquad t=0,1,2,\dots,

where $e\approx2.71828$ is Euler's number. Moreover, sequence A000149 is $p$ -graphical for the parameter consisting of the subscripts of vertices in some $\gamma$ -set of $G$ , over $\mathcal{F}=\{G:G=J_n(x),\ n=1,2,3,\dots\}$ . The source offers a sequence-based conjecture for the domination structure but gives no proof or resolution.

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 calculation claims the proposed set fails to dominate the graph, which would disprove the conjecture, but no independent confirmation is recorded.

Johan Kok proposed the Euler-exponential description in a 2025 experimental study of linear Jaco graphs. The conjecture identifies a minimum dominating set using indices $\lfloor e^t\rfloor$ and extends the sequence claim to finite graphs.

Undated counterexample claim

A calculation identifies $v_{88}$ as having no neighbor in the proposed set, using the indegree formula and the upper-neighbor function $U(i)=2i-d^-(v_i)$ . It further claims infinitely many undominated vertices because $U(i)\sim\varphi i$ while successive proposed indices grow by a factor of $e>\varphi^2$ . This is a complete disproof claim, but it has not been independently verified.

Current status (as of August 2026): the original conjecture has an unverified disproof claim, while no independently verified proof or disproof is recorded.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

The proposed Euler-exponential set is not even a dominating set. In fact, it leaves infinitely many vertices undominated.

For the infinite linear Jaco graph, the established indegree formula is

d^-(v_i) = \left\lfloor\frac{2(i+1)}{3+\sqrt5}\right\rfloor.

For $i<j$ , its underlying undirected adjacency rule is

v_iv_j\in E \quad\Longleftrightarrow\quad j\le U(i), \qquad U(i)=2i-d^-(v_i).

Since successive indegrees differ by zero or one, $U(i)$ is strictly increasing.

The proposed set is

X=\{v_{\lfloor e^t\rfloor}:t=0,1,2,\ldots\} =\{v_1,v_2,v_7,v_{20},v_{54},v_{148},\ldots\}.

Consider $v_{88}$ . The last selected index preceding 88 is 54, and

d^-(v_{54})=21, \qquad U(54)=2\cdot54-21=87<88.

By monotonicity of $U$ , no selected vertex of index at most 54 is adjacent to $v_{88}$ .

On the other hand,

d^-(v_{88})=33, \qquad U(88)=2\cdot88-33=143<148.

Thus no selected vertex of index at least 148 is adjacent to $v_{88}$ . Since $v_{88}\notin X$ ,

N[v_{88}]\cap X=\varnothing.

Therefore $X$ is not dominating and cannot be a minimum dominating set.

Moreover, put $\varphi=(1+\sqrt5)/2$ and $a_t=\lfloor e^t\rfloor$ . The indegree formula gives

U(i)=\varphi i+O(1),

whereas

a_{t+1}=e\,a_t+O(1).

Since $e>\varphi^2$ ,

U\bigl(U(a_t)+1\bigr) = \varphi^2a_t+O(1) < a_{t+1}

for all sufficiently large $t$ . Hence each vertex

v_{U(a_t)+1}

has no neighbor among the proposed indices at most $a_t$ or among those at least $a_{t+1}$ . Consequently the conjectured set misses infinitely many vertices.