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

From papers

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

X={v1}{v2,v7,v20,v54,}X=\{v_1\}\cup\{v_2,v_7,v_{20},v_{54},\dots\}

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

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

where e2.71828e\approx2.71828 is Euler's number. Moreover, sequence A000149 is pp-graphical for the parameter consisting of the subscripts of vertices in some γ\gamma-set of GG, over F={G:G=Jn(x), n=1,2,3,}\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.

Progress summary

Open

No publicly documented proof, disproof, or substantive progress on this conjecture was found.

No public discussion, proof, counterexample, or published progress was found for the conjecture.

Current status (as of August 2026): the conjecture remains open, with no recorded public progress or resolution.

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

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(vi)=2(i+1)3+5.d^-(v_i) = \left\lfloor\frac{2(i+1)}{3+\sqrt5}\right\rfloor.

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

vivjEjU(i),U(i)=2id(vi).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)U(i) is strictly increasing.

The proposed set is

X={vet:t=0,1,2,}={v1,v2,v7,v20,v54,v148,}.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 v88v_{88}. The last selected index preceding 88 is 54, and

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

By monotonicity of UU, no selected vertex of index at most 54 is adjacent to v88v_{88}.

On the other hand,

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

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

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

Therefore XX is not dominating and cannot be a minimum dominating set.

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

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

whereas

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

Since e>φ2e>\varphi^2,

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

for all sufficiently large tt. Hence each vertex

vU(at)+1v_{U(a_t)+1}

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

0 endorsements
Shivam Patel ·