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

From papers

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.

Progress summary

Open

The proposed exact rule for the largest degree in these finite graphs remains an unproved conjecture, with no public proof or counterexample found.

The conjecture asserts an exact formula for the maximum degree of each finite linear Jaco graph, namely $\Delta(J_n(x))=\left\lfloor\frac{2(n+2)}{1+\sqrt{5}}\right\rfloor-1$ , and claims that sequence A319433 records these values. The supplied sources leave this statement unresolved.

Known results

A 2015 study proves general structural properties, including monotonicity of maximum degree under passage from order $k$ to order $n$ when $k\le n$ , but not the conjectured formula.

2025 conjecture restatement

The relevant 2025 paper derives an expression from vertex-degree formulas and identifies the remaining issue as a floor-function identity. It explicitly leaves proofs or disproofs for future work; no counterexample, claimed solution, or independent verification is reported.

Current status (as of August 2026): The formula and the $p$ -graphical claim remain open; no publicly documented proof, disproof, or verified settlement was found.

Sources

arxiv.org

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

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.

1 week ago

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.

0 endorsements

Shivam Patel · 23 hours ago