Let J_n(x) be the finite linear Jaco graph of order n, and let Delta(J_n(x)) denote its maximum degree. 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. Maximum-degree formula conjecture. For n=2,3,4,…, the maximum degrees are given by sequence A319433, with Delta(J_n(x))=lfloor frac2(n+2)1+√5rfloor-1. Moreover, sequence A319433 is p-graphical for p(G)=Delta(G) and F=G:G=J_n(x), n=1,2,3,…. The conjecture reduces to proving the stated floor-function identity relating the maximum degree to the vertex-degree formula; its status is not resolved in the supplied source.

Maximum-degree formula conjecture for finite linear Jaco graphs

At least 7 years old · documented by 2018

Let $J_n(x)$ be the finite linear Jaco graph of order $n$ , and let $\Delta(J_n(x))$ denote its 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}$ . Maximum-degree formula conjecture. For $n=2,3,4,\dots$ , the maximum degrees are given by sequence A319433, with

\Delta(J_n(x))=\left\lfloor\frac{2(n+2)}{1+\sqrt{5}}\right\rfloor-1.

Moreover, sequence A319433 is $p$ -graphical for $p(G)=\Delta(G)$ and $\mathcal{F}=\{G:G=J_n(x),\ n=1,2,3,\dots\}$ . The conjecture reduces to proving the stated floor-function identity relating the maximum degree to the vertex-degree formula; its status 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).

Additional references

4 papers in this index state this conjecture (2018–2025). The statement above is taken from the most recent of them; the others are arXiv:2308.01258, arXiv:2010.15751, arXiv:1801.07021.

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

An unverified posted argument claims a complete proof of the maximum-degree formula, while the published source still presents it as an open conjecture.

The conjecture, stated by Johan Kok in 2025, asserts that the largest degree in each finite linear Jaco graph is

\Delta(J_n(x))=\left\lfloor\frac{2(n+2)}{1+\sqrt{5}}\right\rfloor-1.

It also identifies sequence A319433 as the corresponding degree sequence.

Known results

The 2025 paper labels the formula Conjecture 2.2 and says the required floor-function identity remains unproved.
A 2015 paper proves general structural and monotonicity results for maximum degrees, but not this formula.
A 2014 paper likewise treats related maximum-degree statements for $J_n(1)$ as conjectural.

Posted attempt

A posted argument claims a complete proof, deriving an exact finite-graph degree formula from the indegree formula and a complementary-floor identity; it also claims the result extends to $n=1$ . The argument has not been independently verified.

Current status (as of August 2026): The published literature leaves the conjecture open, while a complete proof has been posted but remains unverified.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

The conjectured formula holds for every $n\ge2$ , and in fact extends to $n=1$ .

Put

\varphi=\frac{1+\sqrt5}{2}.

The established indegree formula for the infinite linear Jaco graph is

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

By the graph's defining adjacency rule, the forward neighbors of $v_i$ are exactly

v_{i+1},\ldots,v_{i+b_i}, \qquad b_i=i-d_i^-.

Since

\frac1\varphi+\frac1{\varphi^2}=1

and $(i+1)/\varphi$ is irrational, the complementary-floor identity gives

\left\lfloor\frac{i+1}{\varphi}\right\rfloor + \left\lfloor\frac{i+1}{\varphi^2}\right\rfloor =i.

Therefore

b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor.

In the finite graph $J_n(x)$ , only forward neighbors with index at most $n$ remain. Hence every vertex has the exact degree

\deg_{J_n(x)}(v_i) = d_i^-+\min\{b_i,n-i\} = \min\left\{ i,\ n-\left\lfloor\frac{i+1}{\varphi}\right\rfloor \right\}. \tag{1}

The sequence $b_i$ is nondecreasing. Thus, for each positive integer $r$ ,

\begin{aligned} \Delta(J_n(x))\ge r &\iff \exists i\ge r:\ b_i\le n-r\\ &\iff r+b_r\le n\\ &\iff r+\left\lfloor\frac{r+1}{\varphi}\right\rfloor\le n\\ &\iff \left\lfloor(r+1)\varphi\right\rfloor\le n+1\\ &\iff (r+1)\varphi<n+2. \end{aligned}

The last equivalence uses the irrationality of $(r+1)\varphi$ . Since $(n+2)/\varphi$ is likewise irrational, the largest admissible $r$ is

\boxed{ \Delta(J_n(x)) = \left\lfloor\frac{n+2}{\varphi}\right\rfloor-1 = \left\lfloor\frac{2(n+2)}{1+\sqrt5}\right\rfloor-1. }

For $n=1$ , both sides are zero directly. Equation (1) also gives the complete degree sequence, strengthening the conjectured maximum-degree formula.