WorksMathematics
Short Paper No. 1: Relation between integer sequence A319433 and the maximum degrees of finite linear Jaco graphs
Abstract
This short paper presents the interesting relation between integer sequence A319433 in https://oeis.org and the maximum degrees of the family of finite linear Jaco graphs where . The result first appeared as a conjecture. Subsequently, a proof through AI-assisted mathematical reasoning came to the fore. Appropriate clarity remarks follow in the main text. It appears that -like floor function plays an important role in the analysis of the graph structural properties of the family of finite linear Jaco graphs.
Preliminary remarks
Numerous conjectures appeared in [3]. Subsequently the first author tested the ability of AI-assisted mathematical reasoning technology (under development) to present valid proofs of the conjectures. The second author evaluated the proofs for correctness. Both authors co-authored this manuscript. See § 6.
Most of introduction replicates much which is found in [3]. The reason is twofold. Firstly, it makes this short paper self-contained and secondly, the arXived manuscript has not officially been published in any journal. This first, in a series of short papers is formally submitted to undergo rigorous peer review as well.
Introduction
It is assumed that the reader is familiar with the basic terminology and notions of graph theory. See [1, 2, 10]. When the context is clear, notation such as will be abbreviated to and so on. In 2014 the authors Kok et al. introduced the family of directed finite linear Jaco graphs. See [4, 5] and the references thereto. Unless stated otherwise, all graphs in this short paper will be the underlying graph of the directed finite linear Jaco graphs (for reference, linear Jaco graphs).
The motivation for the study in [3] does not lie in possible applications of linear Jaco graphs per se but rather in a new research avenue i.e. relations between some integer sequences and certain parameters of linear Jaco graphs. In addition to the aforesaid the validation of AI-assisted mathematical reasoning to prove of such conjectured relations has come to the fore. Clearly, the aforesaid has real world applications. Recall that a sequence of non-negative integers, say
is said to be graphical if there exists a simple graph which has degree sequence . Put differently, is graphical in respect of the vertex degrees if there exists a simple graph which has degree sequence . Note that could be either a random or a definable sequence. A definable sequence can only be generated from a closed or recursive formula. A generalization can be investigated. That is, if is a graph parameter (independence number, domination number, chromatic number, hub number and so on) then a definable sequence (finite or infinite) is -graphical if a family (or set) or subset of a family of simple graphs exists, say such that,
Note that the notion of a -graphical sequence extends over graph parameters (global as mentioned above) and parameters related to graph elements (local), for example the eccentricity of a vertex, , the degree of a vertex, , the distance between two distinct edges and so on. For the aforesaid the notation is or . The parameter may also be a hybrid such as vertex-edge domination and edge-vertex domination (see [8]) or it may concern subsets of or and so on. The corresponding notation will be or or where or .
Example: The infinite integer sequence is -graphical for (chromatic number of graph) since exists and
Note 2.1. The notion of graphical degree sequences is generalized to graphical graph parametric sequences. This avenue for further research remains open.
On linear Jaco graphs
Readers are referred to [4, 5] for the formal definitions of and . Since our interest lies with the underlying graph we recall the construction method as explained in [6] with some additional refinement.
Construction method to obtain , :
(a) Let , and .
(b) Let the empty graph (edgeless graph) of order be denoted by . Let and let where .
(c) By normal consecutive step-count for do as follows:
To obtain add the edges with a maximum such that, .
(d) After completion of step-count label the resultant graph . Note that is a simple connected undirected graph.
Recall from [6] that for a given the open neighborhood of in a given by: where and . Also let and and let . The aforesaid yields .
All sequences mentioned in this paper are found in [9]. Recall that Wagner [4, 6] identified that in accordance with sequence A060144 the result , holds. Put differently, the sequence A060144 is -graphical where , and or simply .
Maximum degree of ,
In [3] it is conjectured (see Conjecture 2.2 in [3]) that for the finite linear Jaco graphs , the respective maximum degrees are yielded by the sequence A319433 with closed formula ,
Furthermore, it implies that sequence A319433 is -graphical where and .
The AI-assisted mathematical reasoning included and it is easy to see why. Since it follows that .
Therefore, the conjecture may be considered for The AI-assisted mathematical reasoning utilized the conventional directed linear Jaco graph with the notation thereof as found in the founding papers. See [4, 5]. Adapting the proof to the notation in [3] is easy in that:
Note that for a sufficiently large (which always exists), .
AI-assisted mathematical reasoning
It is known that the golden ratio is,
The known identities which will be used frequently are,
Note that since is irrational, every nonzero integer multiple of , , is irrational. Also, for a given the largest such that is a neighbor of is called the reach of and denoted by and defined by . It implies that a vertex , is a neighbor of . Consequently,
In a finite linear Jaco graph the degree of a vertex is bounded by . For use later on the next is an important definition.
Definition 4.1. For , define
Lemma 4.1. For integers we have .
Proof. Note that both and are non-integers. However, from the fourth identity i.e. it follows that,
Hence, the identity applies. Therefore,
Lemma 4.2. (Reach identity) For every we have, and in particular, the sequence is strictly increasing.
Proof. From the second identity i.e. it follows that,
Since is an integer it follows that,
This settles the result.
Also, the claim to strict increase follows because hence,
increases by 1 or 2. □
Deriving and
The AI-assisted mathematical reasoning included autonomous proofs of two important results.
Theorem 4.3. For every we have, . Consequently, in we have that, .
Proof. The proof will be by mathematical induction. For , there is no smaller indexed vertex, hence . Also . Thus the result holds for . Assume the results holds for all , . For each the induction hypothesis read with Lemma 4.1 give
By Lemma 4.2, . The adjacency rule permits the edge , when . Since the sequence is strictly increasing, there exists a terminal interval or put differently, a subset of vertices which permits the edges , . Furthermore, is the smallest integer satisfying . Also, . Since is irrational it follows that,
Since is non-integral, the smallest integer strictly greater than is, . Therefore, the largest integer strictly less than is,
So it follows that the number of vertices , such that the edges exist is given by,
By Lemma 4.1 or put differently, . This settles the induction proof of the first part of the theorem. Finally the fact that read together with Lemma 4.1 concludes that which proves the second part of the theorem. □
Note 4.4. Theorem 4.3 independently confirms what Wagner [4, 6] established i.e. because .
Deriving degree of vertex in , , .
Note that for a given , remains a constant in the family of finite linear Jaco graphs , . However, due to truncation to obtain a finite linear Jaco graph , it follows that . The next theorem provides a result for , , .
Theorem 4.5. For every and every and every ,
Proof. By Theorem 4.3 the vertex has and in we have . The neighbors corresponding to are,
In the neighbors corresponding to is limited to a subset of the set . Hence the number (cardinality of permissible subset) of such neighbors is . Hence, . Using it follows that,
By substituting the result is settled. □
Note 4.6. No boundary approximation is involved in Theorem 4.5. Truncation removes precisely those neighbors whose indices exceed . The indices of the forward neighbors corresponding to form a consecutive interval of integers and the number of such integers is exactly .
A scalar threshold for .
Define . By Theorem 4.5 we have . For the sequence is non-decreasing, since it is the floor of a strictly increasing function.
Lemma 4.7. (Threshold characterization) For every and every integer , ,
Proof. From it follows that if and only if there exists an , such that both and . Equivalently, there exists an such that .
Since is non-decreasing there exists an index satisfying
Therefore, if and only if .
Lemma 4.7 is the decisive simplification in that, graph theoretical maximization is replaced by inversion of the one-variable quantity .
Proof of main conjecture.
Theorem 4.8. (Maximum degree of each , ) For every integer we have,
Proof. Case 1: For the result is trivial because .
Case 2: For : By Lemma 4.7 for every with it is true that,
The number is irrational hence, the largest integer below is . Consequently, the largest integer for which is . Since the result is settled.
Conclusion
Theorem 4.8 essentially proves the Conjecture 2.2 in [3]. It can be said that integer sequence A319433 found in [9] is -graphical where and .
AI disclosure
AI-assisted mathematical reasoning technology was used substantially in the mathematical exploration, development of candidate arguments, intermediate verification, and preparation of the source manuscript. The technology was used within an author-directed problem-solving and verification methodology. All resulting mathematical claims and proofs were subsequently reviewed and validated before human drafting of a final manuscript. The human authors take full responsibility for all mathematical statements, proofs, computations, citations, and conclusions presented herein.
After completion of this captioned topic and others found in [3] the first author became aware of an independent AI-proof of Conjecture 2.2 posted by Shivan Patel on the repository MathDB. Accordingly no claim of priority is made here.
Dedication
This short paper is dedicated to late Mr Fransloo Vorster (nicknamed ”Fifi”) who was the teacher of mathematics of the second author at Bellville High School, Western Cape Province, South Africa. The dedication serves to acknowledge the remarkable way in which Mr Vorster could explain the wonders of High School Mathematics. May his soul rest in peace.
References
- [1]J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan Press, London, (1976).
- [2]F. Harary, Graph Theory, Addison-Wesley, Reading MA, (1969).
- [3]J. Kok, Integer sequences with conjectured relation with certain graph parameters of the family of linear Jaco graphs, arXiv:2507.16500 (2025).arxiv.org/abs/2507.16500
- [4]J. Kok, S. Naduvath, C. Kalthavappil, G.K. Augustyni and U.M. Augustine, Special issue on: Reflections on Jaco Graphs, Journal of Informatics and Mathematical Sciences, 8(2), (2016).
- [5]J. Kok, C. Susanth and S.J. Kalayathankal, A study on linear Jaco graphs, Journal of Informatics and Mathematical Sciences, 7(2), 69–80,(2015).arxiv.org/abs/1506.06538
- [6]J. Kok, Research note: Domination of exact deg-centric Jaco graphs, Open Journal of Discrete Applied Mathematics, 8(2), 52–60,(2025).DOI
- [8]K.W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity, Ph.D. thesis, Clemson University, Clemson SC, (1986).
- [9]N.J.A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, https://oeis.org.
- [10]D.B. West, Introduction to graph theory, Prentice Hall of India, New Delhi, (2001).