Delta-set cardinality conjecture for finite linear Jaco graphs

About 1 year old · traced to 2025

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.

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

A 2025 paper conjectured the three classifications, while an unverified posted attempt now claims a complete proof using exact degree formulas and Beatty-sequence identities.

Johan Kok’s July 2025 preprint identifies the orders of finite linear Jaco graphs $J_n(x)$ having $|X|=1$ , $|X|=2$ , or $|X|=3$ with three Wythoff-type sequences. It explicitly presents these identifications as conjectures and leaves proof or disproof open.

Known results

For finite Jaco graphs $J_n(1)$ , the Jaconian set has cardinality at most $3$ (2014).

Posted attempt

A posted argument claims a complete proof: it derives an exact degree formula, characterizes all maximizers through complementary Beatty sequences, and obtains the stated singleton, doubleton, and tripleton order formulas. The argument has not been independently verified, so it does not establish the conjecture.

Current status (as of August 2026): The three sequence classifications remain unproved in the published record, but a complete proof has been claimed publicly and is unverified.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

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.