Delta-set cardinality conjecture for finite linear Jaco graphs

From papers

Let $J_n(x)$ be a finite linear Jaco graph of order $n\geq3$ , and let $X$ be its $\Delta$ -set, equivalently its Jaconian set, consisting of vertices attaining the maximum degree. 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}$ . Delta-set cardinality conjecture. The orders for which $X$ has the following cardinalities are conjectured to be:

(a) for $|X|=1$ , $a(t)=w(t+1)-2$ , $t=1,2,3,\dots$ , where sequence A001950 is the upper Wythoff sequence and

w(t)=\left\lfloor\frac{t(1+\sqrt{5})^2}{4}\right\rfloor;

(b) for $|X|=2$ , sequence A057843, with

a(t)=\left\lfloor\frac{t(1+\sqrt{5})^2}{4}\right\rfloor-3,\qquad t=2,3,4,\dots;

a(t)=2\left\lfloor\frac{t(1+\sqrt{5})^2}{4}\right\rfloor-(t+2),\qquad t=2,3,4,\dots.

These sequences are respectively $p$ -graphical for the parameter $p(G)=|X|$ and $\mathcal{F}=\{G:G=J_n(x),\ n=1,2,3,\dots\}$ . The source presents these as conjectural sequence identifications based on the table of linear Jaco graphs; no resolution is supplied.

Progress summary

Open

A 2025 paper proposed a pattern for when these graphs have one, two, or three highest-degree vertices, but no proof or counterexample has appeared.

The conjecture identifies the orders of finite linear Jaco graphs for which the maximum-degree vertex set has cardinality $1$ , $2$ , or $3$ , using Wythoff-type sequences including $A001950$ , $A057843$ , and an adapted $A134859$ . It was presented in a 2025 preprint as an experimentally observed pattern, not as a theorem.

July 2025 preprint

The paper reports the three sequence identifications for the parameter $p(G)=|X|$ and explicitly leaves their proof or disproof to future work. No retrieved source supplies a proof, counterexample, refutation, or claimed solution.

Current status (as of August 2026): The three sequence classifications remain conjectural; no proof or disproof of the stated finite linear Jaco-graph problem is publicly recorded.

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

1 week ago

All three asserted classifications follow from the exact finite-graph degree sequence and complementary Beatty sequences.

Put

\varphi=\frac{1+\sqrt5}{2}, \qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor.

The known Jaco-graph indegree formula yields

\deg_{J_n(x)}(v_i)=\min\{i,n-b_i\}. \tag{1}

Write

d=\Delta(J_n(x)),\qquad h=n-d.

Since $b_i$ is nondecreasing, the ENTIRE maximum-degree set is

X_n = \{v_i:i\ge d,\ b_i\le h\}. \tag{2}

The plateau on which $b_i=h$ consists precisely of

\lfloor h\varphi\rfloor \le i\le \lfloor(h+1)\varphi\rfloor-1. \tag{3}

Its length is one or two; by complementary Beatty sequences, it has length two exactly when

h=\lfloor t\varphi\rfloor

for some positive integer $t$ . Maximality of $d$ implies $b_{d+1}\ge h$ , so (2) contains at most one index preceding this plateau. Therefore $|X_n|\le3$ .

Singleton case. Equation (2) is a singleton precisely when $d$ is the last index of the $h$ -plateau:

d=\lfloor(h+1)\varphi\rfloor-1.

Consequently

n=d+h = \lfloor(h+1)\varphi^2\rfloor-2.

This is exactly the claimed upper-Wythoff sequence

n=w(t+1)-2,\qquad w(s)=\lfloor s\varphi^2\rfloor.

Doubleton case. A two-vertex maximum-degree set at order $n$ becomes a singleton maximum-degree set at order $n+1$ , and conversely. Indeed, if

X_n=\{v_d,v_{d+1}\},

then $b_{d+1}\le h<b_{d+2}$ , so the unique maximizer at order $n+1$ is $v_{d+1}$ . Reversing the same argument gives the converse. Subtracting one from the singleton orders therefore yields

n=\lfloor t\varphi^2\rfloor-3.

The source lists $t\ge2$ : its first term $t=2$ gives $n=2$ , where $J_2$ indeed has two maximum-degree vertices, although this lies outside the global stated restriction $n\ge3$ . Within that restriction one simply takes $t\ge3$ .

Tripleton case. Equation (2) has three elements precisely when the $h$ -plateau has length two and begins immediately after $d$ . Write

h=\lfloor t\varphi\rfloor.

The complementary-floor identity gives

\lfloor h\varphi\rfloor=t+h-1,

d=t+h-2,\qquad n=d+h=t+2h-2.

Since $\lfloor t\varphi^2\rfloor=t+\lfloor t\varphi\rfloor=t+h$ , this becomes

n=2\lfloor t\varphi^2\rfloor-(t+2), \qquad t\ge2.

Thus the singleton, doubleton, and tripleton orders are exactly the three sequences in the conjecture, with the harmless $n=2$ boundary term interpreted as above.

0 endorsements

Shivam Patel · 23 hours ago