A Study on Linear Jaco Graphs

(Johan Kok, Susanth C, Sunny Joseph Kalayathankal)111Affiliation of authors:
Johan Kok (Tshwane Metropolitan Police Department), City of Tshwane, Republic
of South Africa
e-mail<EMAIL_ADDRESS>

Susanth C (Department of Mathematics, Vidya Academy of Science and
Technology), Thalakkottukara, Thrissur-680501, Republic of India
e-mail<EMAIL_ADDRESS>

Sunny Joseph Kalayathankal (Department of Mathematics, Kuriakose Elias
College), Mannanam, Kottayam- 686561, Kerala, Republic of India
e-mail<EMAIL_ADDRESS>
###### Abstract

We introduce the concept of a family of finite directed graphs (_positive
integer order,_ $f(x)=mx+c;x,m\in\mathbb{N}$ and $c\in\mathbb{N}_{0})$ which
are directed graphs derived from an infinite directed graph called the
$f(x)$-root digraph. The $f(x)$-root digraph has four fundamental properties
which are; $V(J_{\infty}(f(x)))=\\{v_{i}:i\in\mathbb{N}\\}$ and, if $v_{j}$ is
the head of an arc then the tail is always a vertex $v_{i},i<j$ and, if
$v_{k}$ for smallest $k\in\mathbb{N}$ is a tail vertex then all vertices
$v_{\ell},k<\ell<j$ are tails of arcs to $v_{j}$ and finally, the degree of
vertex $v_{k}$ is $d(v_{k})=mk+c.$ The family of finite directed graphs are
those limited to $n\in\mathbb{N}$ vertices by lobbing off all vertices (and
corresponding arcs) $v_{t},t>n.$ Hence, trivially we have $d(v_{i})\leq mi+c$
for $i\in\mathbb{N}.$ It is meant to be an _introductory paper_ to encourage
further research.

Keywords: Linear function Jaco graph, Hope graph, directed graph, Jaconian
vertex, Jaconian set

AMS Classification Numbers: 05C07, 05C38, 05C78

##  1 Introduction

For general notation and concepts in graph theory, we refer to [2, 3, 4, 8].
All graphs mentioned in this paper are simple, connected finite and directed
graphs unless mentioned otherwise. We introduce the concept of a family of
finite linear Jaco graphs (_positive integer order,_
$f(x)=mx+c;x,m\in\mathbb{N}$ and $c\in\mathbb{N}_{0})$ which are directed
graphs derived from the infinite linear Jaco graph (_positive integer order,_
$f(x)=mx+c;x,m\in\mathbb{N}$ and $c\in\mathbb{N}_{0})$, called the $f(x)$-root
Jaco graph. In this study we generalise a number of results found in [6, 7]
because the aforesaid studies relate to special cases of linear Jaco graphs.

######  Definition 1.1.

Let $f(x)=mx+c;x,m\in\mathbb{N},$ $c\in\mathbb{N}_{0}.$ The family of infinite
linear Jaco graphs denoted by $\\{J_{\infty}(f(x)):f(x)=mx+c;x,m\in\mathbb{N}$
and $c\in\mathbb{N}_{0}\\}$ is defined by
$V(J_{\infty}(f(x)))=\\{v_{i}:i\in\mathbb{N}\\}$,
$A(J_{\infty}(f(x)))\subseteq\\{(v_{i},v_{j}):i,j\in\mathbb{N},i<j\\}$ and
$(v_{i},v_{j})\in A(J_{\infty}(f(x)))$ if and only if
$(f(i)+i)-d^{-}(v_{i})\geq j.$

From definition 1.1 we note the $f(x)$-root Jaco graph has four fundamental
properties which are;

(a) $V(J_{\infty}(f(x)))=\\{v_{i}:i\in\mathbb{N}\\}$ and,
(b) if $v_{j}$ is the head of an arc then the tail is always a vertex
$v_{i},i<j$ and,
(c) if $v_{k}$ for smallest $k\in\mathbb{N}$ is a tail vertex then all
vertices $v_{\ell},k<\ell<j$ are tails of arcs to $v_{j}$ and finally,
(d) the degree of vertex $k$ is $d(v_{k})=mk+c.$

######  Definition 1.2.

For $f(x)=mx+c;x,m\in\mathbb{N}$ and $c\in\mathbb{N}_{0},$ we define the
series $(c_{f(x),n})_{n\in\mathbb{N}_{0}}$ by

$c_{f(x),0}=0,$ $c_{f(x),1}=1,$ $c_{f(x),n\geq 2}=\min\\{k<n:mk+c_{f(x),k}\geq
n\\}$.

The connection between the $f(x)$-root digraph $J_{\infty}(f(x))$ and the
series $(c_{f(x),n})_{n\in\mathbb{N}_{0}}$ is explained by the following
lemma.

######  Lemma 1.1.

Consider the Jaco graph $J_{\infty}(f(x))$ and let $n\in\mathbb{N}$ then the
following hold:
(a) $d^{+}(v_{n})+d^{-}(v_{n})=f(n).$
(b) $d^{-}(v_{n+1})\in\\{d^{-}(v_{n}),\,d^{-}(v_{n})+1\\}.$
(c) If $(v_{i},v_{k})\in A(J_{\infty}(f(x)))$ and $i<j<k,$ then
$(v_{j},v_{k})\in A(J_{\infty}(f(x))).$
(d) $d^{+}(v_{n})=((m-1)n+c)+c_{f(x),n},$ $n\geq 2.$

###### Proof.

(a) Invoking definition 1.1 and since $d^{+}(v_{n})=(f(n)+n)-n-d^{-}(v_{n}),$
the result is obvious.
(b), (c) We prove (b) and (c) simultaneously through induction on $n.$ First
of all, $d^{-}(v_{1})=0$ implying $d^{-}(v_{2})=1=d^{-}(v_{1})+1.$

Let $n\geq 2$ and assume result (b) holds for $m\leq n$ and (c) holds for
$m\leq n-1.$ In particular, $d^{-}(v_{n})>0.$ Let $\ell<n$ be minimal with
$(v_{\ell},v_{n})\in A(J_{\infty}(f(x))),$ so
$(f(\ell)+\ell)-d^{-}(v_{\ell})\geq n.$ Let $\ell<j<n.$ By induction, we have
$d^{-}(v_{\ell})\leq d^{-}(v_{j})\leq d^{-}(v_{\ell})+j-\ell$ and
$(f(j)+j)-d^{-}(v_{j})\geq n.$ Hence, and by choice of $\ell,$ we have
$(v_{k},v_{n})\in A(J_{\infty}(f(x)))$ if and only if $\ell\leq k<n,$ hence
result $(c)$ is valid for $n,$ while $d^{-}(v_{n})=n-\ell$ and
$d^{+}(v_{n})=(f(n)+n)-(n-\ell)=f(n)+\ell.$

If $(f(\ell)+\ell)-d^{-}(v_{\ell})\geq n+1,$ then $\ell$ is minimal with
$(f(\ell)+\ell)-d^{-}(v_{\ell})\geq n+1.$ If
$(f(\ell)+\ell)-d^{-}(v_{\ell})=n,$ we still, as $\ell+1\leq n,$ have
$d^{-}(v_{\ell+1})\in\\{d^{-}(v_{\ell}),\,d^{-}(v_{\ell)+1}\\}$ and
$(f(\ell+1)+\ell+1)-d^{-}(v_{\ell+1})\geq n+1.$ Either way,
$(v_{\ell+1},v_{n+1})\in A(J_{\infty}(f(x))).$ If $\ell+1<j<n,$ then induction
yields $d^{-}(v_{\ell+1})\leq d^{-}(v_{j})\leq d^{-}(v_{\ell+1})+(j-\ell-1)$
and $(f(j)+j)-d^{-}(v_{j})\geq n+1.$ As $d^{-}(v_{n})\leq
n-1,(v_{n},v_{n+1})\in A(J_{\infty}(f(x))),$ so $(v_{k},v_{n+1})\in
A(J_{\infty}(f(x)))$ whenever $\ell+1\leq k\leq n.$ Depending on whether
$(v_{\ell},v_{n+1})\in A(J_{\infty}(f(x)))$ or not, we obtain
$d^{-}(v_{n+1})=n+1-\ell=(n-\ell)+1=d^{-}(v_{\ell})+1$ or
$d^{-}(v_{n+1})=n+1-(\ell+1)=d^{-}(v_{n}).$ (d) Let $n\geq 3,$ and, as before,
choose $\ell$ minimal with $(v_{\ell},v_{n})\in A(J_{\infty}(a)).$ We prove
the result by induction on $n$ and apply arguments very similar to the ones
already used. First of all, $d^{-}(v_{1})=0,$ and
$d^{+}(v_{1})=f(1)=((m-1)1+c)+c_{f(x),1}.$ Now let $n>1,$ and, as before,
choose $\ell$ minimal such that $(v_{\ell},v_{n})\in A(J_{\infty}(a)).$ By
$(a)$ and $(c),$ $d^{-}(v_{n})=n-\ell,$ and
$d^{+}(v_{n})=(mn+c)-n+\ell=((m-1)n+c)+\ell.$ Induction yields that
$d^{+}(v_{k})=d^{+}(v_{k})=((m-1)k+c)+c_{f(x),k},$ whenever $k<n.$ The
definition of $\ell$ says that $\ell$ is minimal with
$\ell+d^{+}(v_{\ell})=((m-1)\ell+c)+c_{f(x),\ell}\geq n,$ which means that
$\ell=c_{f(x),n}.$ ∎

######  Corollary 1.2.

Note that $(a)$ and $(b)$ of Lemma 1.1 entail that
$d^{-}(v_{n+1})=(n+1)-c_{f(x),n+1}\in\\{n-c_{f(x),n},n-c_{f(x),n}+1\\}$ and
that $(d)$ then implies that the series $(c_{f(x),n})$ are well-defined and
ascending, more specifically, $c_{f(x),n+1}\in\\{c_{f(x),n},c_{f(x),n}+1\\},$
($n\in\mathbb{N}_{0}$).

Consider the function $g(x)=m_{1}x+c_{1};x,m_{1}\in\mathbb{N},$
$c_{1}\in\mathbb{N}_{0}.$ In respect of $f(x)$ and $g(x)$ we have the
following proposition.

######  Proposition 1.3.

Let $k\in\mathbb{N},$ and $0\leq g(x)<f(x).$ Then
$c_{f(x),mk+c_{f(x),k}-g(x)}=k.$

###### Proof.

Let $mk+c_{f(x),k}-g(x)=\ell.$ Certainly, $mk+c_{f(x),k}\geq\ell$ hence,
$c_{\ell}\leq k.$ On the other hand,
$((m-1)k+c)+c_{f(x),k}=(mk+c)+c_{f(x),k}-k<\ell,$ so Corollary 1.2 says
$((m-1)k+c)+c_{f(x),k-1}<\ell$ and $c_{\ell}=k.$ ∎

##  2 Finite Linear Jaco Graphs $\\{J_{n}(f(x)):f(x)=mx+c;x,m\in\mathbb{N}$
and $c\in\mathbb{N}_{0}\\}$

The family of finite linear Jaco graphs are those limited to $n\in\mathbb{N}$
vertices by lobbing off all vertices (and corresponding arcs) $v_{t},t>n.$
Hence, trivially we have $d(v_{i})\leq f(i)$ for $i\in\mathbb{N}.$

######  Definition 2.1.

The family of finite linear Jaco graphs denoted by
$\\{J_{n}(f(x)):f(x)=mx+c;x,m\in\mathbb{N}$ and $c\in\mathbb{N}_{0}\\}$ is the
defined by $V(J_{n}(f(x)))=\\{v_{i}:i\in\mathbb{N},i\leq n\\}$,
$A(J_{n}(f(x)))\subseteq\\{(v_{i},v_{j})|i,j\in\mathbb{N},i<j\leq n\\}$ and
$(v_{i},v_{j})\in A(J_{n}(f(x)))$ if and only if $(f(i)+i)-d^{-}(v_{i})\geq
j.$

######  Definition 2.2.

Vertices with degree $\Delta(J_{n}(f(x)))$ is called Jaconian vertices and the
set of vertices with maximum degree is called the Jaconian set of the linear
Jaco graph $J_{n}(f(x)),$ and denoted, $\mathbb{J}(J_{n}(f(x)))$ or,
$\mathbb{J}_{n}(f(x))$ for brevity.

######  Definition 2.3.

The lowest numbered (indexed) Jaconian vertex is called the prime Jaconian
vertex of a Jaco graph.

######  Definition 2.4.

If $v_{i}$ is the prime Jaconian vertex, the complete subgraph on vertices
$v_{i+1},v_{i+2},\\\ \cdots,v_{n}$ is called the Hope subgraph of a linear
Jaco graph and denoted, $\mathbb{H}(J_{n}(f(x)))$ or, $\mathbb{H}_{n}(f(x))$
for brevity.

Property 1: From the definition of a linear Jaco graph $J_{n}(f(x)),$ it
follows that, if for the prime Jaconian vertex $v_{i},$ we have
$d(v_{i})=f(i)$ then in the underlying Jaco graph denoted $J_{n}^{*}(f(x))$ we
have $d(v_{m})=f(m)$ for all $m\in\\{1,2,3,\cdots,i\\}.$

Property 2: From the definition of a linear Jaco graph $J_{n}(f(x)),$ it
follows that $\Delta(J_{k}(f(x)))\leq\Delta(J_{n}(f(x)))$ for all $k\leq n.$

Property 3: From the definition of a linear Jaco graph $J_{n}(f(x)),$ it
follows that the lowest degree attained by all Jaco graphs is
$0\leq\delta(J_{n}(f(x)))\leq f(1).$

Property 4: The $d^{-}(v_{k})$ for any vertex $v_{k}$ of a linear Jaco graph
$J_{n}(f(x)),n\geq k$ is equal to $d(v_{k})$ in the underlying Jaco graph
$J^{*}_{k}(f(x)).$

Note that henceforth, when the context is clear we interchangeably refer to a
linear Jaco graph $J_{n}(f(x)),$ (directed) and the underlying Jaco graph
$J^{*}_{n}(f(x)),$ (undirected) as a _Jaco graph_. Similar, when the context
is clear we refer to either _arcs_ or _edges_.

Illustration 1. Figure 1 depicts the Jaco graph $J_{11}(f(x)),$ $f(x)=2x+1.$
We note that vertex $v_{4}$ is the prime Jaconian vertex and
$\mathbb{J}_{11}(f(x))=\\{v_{4},v_{5},v_{6}\\}.$

Figure 1:

######  Lemma 2.1.

For the Jaco graphs $J_{i}(f(x)),i\in\\{1,2,3,...,f(1)+1\\}$ we have
$\Delta(J_{i}(f(x)))=i-1$ and $\mathbb{J}(J_{i}(f(x)))=\\{v_{k}:1\leq k\leq
i\\}=V(J_{i}(f(x))).$

###### Proof.

If $t=f(1)+1$ then, $((f(1)+1)+1)-d^{-}(v_{1})>(f(1)+1)$ so from definition
2.1 it follows that the arcs $(v_{1},v_{i}),i=2,3,...,(f(1)+1)$ exist. It then
follows that all arcs $(v_{i},v_{j}),i<j$ exist. So the underlying graph
$J^{*}_{f(1)+1}(f(x))$ is the complete graph $K_{f(1)+1}.$ Since
$\Delta(J_{f(1)+1}(f(x)))=(f(1)+1)-1=f(1)$ and we have $d(v_{i})=f(1)$ for all
vertices in $K_{f(1)+1},$ it follows that $\Delta(J_{f(1)+1}(f(x)))=f(1)$ and
$\mathbb{J}(J_{f(1)+1}(f(x)))=\\{v_{k}:1\leq k\leq
f(1)\\}=V(J_{f(1)+1}(f(x))).$ The result follows similarly for $t<f(1)+1.$ ∎

######  Proposition 2.2.

For the Jaco graphs $J_{f(i)}(f(x)),$ $1\leq i\leq f(1)$ the prime Jaconian
vertex is the vertex $v_{i}$ and
$\mathbb{J}_{f(i)}(f(x))=\\{v_{\ell}:i\leq\ell\leq f(1)+1\\}.$

###### Proof.

Consider the Jaco graph $J_{f(1)}(f(x)).$ It follows that the induced subgraph
$J^{\prime}=\langle v_{i};1\leq i\leq v_{f(1)+1}\rangle$ is the complete graph
$K_{f(1)+1},$ hence $d_{J^{\prime}}(v_{i})=f(1),$ $1\leq i\leq f(1)+1.$ It
follows immediately that $v_{1}$ is the prime Jaconian vertex of $J^{\prime}$
and $\mathbb{J}(J^{\prime})=\\{v_{\ell}:1\leq\ell\leq f(1)+1\\}.$

Also $f(i)>f(1)$, $2\leq i\leq f(1)$ so besides the arcs in $J^{\prime}$,
$v_{i}$ has additional arcs $(v_{i},v_{s});f(1)+2\leq s\leq f(i)+1$ in
$J_{f(i)+1}(f(x)).$ This amounts to $(f(i)-f(1))-1$ additional arcs $\forall
v_{\ell},$ $i\leq\ell\leq f(1)$ in $J_{f(i)+1}(f(x)).$ Clearly $i$ is minimal
such that arc $(v_{i},v_{f(i)+1})$ exists so $v_{i}$ is the prime Jaconian
vertex of the Jaco graph $J_{f(i)+1}(f(x)).$

Because $d_{J^{\prime}}((v_{\ell})=f(1),$ $i\leq\ell\leq f(1)+1$ it follows
immediately that
$d_{J^{\prime}}(v_{\ell})+(f(i)-f(1))-1=d_{J^{\prime}}(v_{i})+(f(i)-f(1))-1$
in $J_{f(i)+1}(f(x)).$ Hence,
$\mathbb{J}_{f(i)}(f(x))=\\{v_{\ell}:i\leq\ell\leq f(1)+1\\}.$ ∎

######  Lemma 2.3.

If in a Jaco graph $J_{n}(f(x)),$ and for smallest $i,$ we have
$d(v_{i})=f(i)$ and the arc $(v_{i},v_{n})$ is defined, then $v_{i}$ is the
prime Jaconian vertex of $J_{n}(f(x)).$

###### Proof.

If in the construction of a Jaco graph $J_{n}(f(x)),$ and for smallest $i,$
the arc $(v_{i},v_{n})$ is defined, we have that in the underlying graph
$J^{*}_{n}(f(x))$, $d(v_{i})\leq f(i)$ and $d(v_{j})\leq d(v_{i})$ for all
$j>i$. So it follows that $d(v_{i})=\Delta(J_{n}(f(i)))$ so $v_{i}$ is the
prime Jaconian vertex of $J_{n}(f(x)).$ ∎

######  Lemma 2.4.

For all Jaco graphs $J_{n}(f(x)),$ $n\geq 2$ and, $v_{i},v_{i-1}\in
V(J_{n}(f(x)))$ we have in the Jaco graph $J^{*}_{n}(f(x)),$ that
$|(d(v_{i})-d(v_{i-1})|\leq m.$

###### Proof.

Clearly, $max|(d(v_{i})-d(v_{i-1})|=f(i)-f(i-1)=mi+c-(m(i-1)+c)=m$ hence,
$|(d(v_{i})-d(v_{i-1})|\leq m.$ ∎

######  Proposition 2.5.

For the Jaco graph $J_{f(i)}(f(x)),$ $i\geq f(1)+1$ the prime Jaconian vertex
is a vertex $v_{j}$, $j\leq i.$

###### Proof.

We have that $f(i)-f(i-1)\geq 1.$ From Lemma 1.1(b) it follows that
$d^{-}(v_{i})=d^{-}(v_{i-1})$ or $d^{-}(v_{i-1})+1.$
Case 1: Let $f(i)-f(i-1)=1.$
Subcase 1.1: Let $d^{-}(v_{i})=d^{-}(v_{i-1}).$ It follows that
$d_{J_{f(i)}}(v_{i-1})=d_{J_{f(i)}}(v_{i})+1$ hence $v_{i-1}$ is the prime
Jaconian vertex. Let $j=i-1$, so $j<i.$
Subcase 1.2: Let $d^{-}(v_{i})=d^{-}(v_{i-1})+1.$ It follows that
$d_{J_{f(i)}}(v_{i-1})=d_{J_{f(i)}}(v_{i})$ hence $v_{i-1}$ is the prime
Jaconian vertex. Let $j=i-1$, so $j<i.$
Case 1: Let $f(i)-f(i-1)=2.$
Subcase 2.1: Let $d^{-}(v_{i})=d^{-}(v_{i-1}).$ It follows that
$d_{J_{f(i)}}(v_{i-1})=d_{J_{f(i)}}(v_{i})$ hence $v_{i-1}$ is the prime
Jaconian vertex. Let $j=i-1$, so $j<i.$
Subcase 1.2: Let $d^{-}(v_{i})=d^{-}(v_{i-1})+1.$ It follows that
$d_{J_{f(i)}}(v_{i})=d_{J_{f(i)}}(v_{i-1})+1$ hence $v_{i}$ is the prime
Jaconian vertex. So equality holds.
By Similar reasoning it follows that for all $f(i)-f(i-1)\geq 3$ vetex $v_{i}$
is the prime Jaconian vertex hence, the result is settled. ∎

Note that the value of $\Delta(J_{n}(f(x)))$ might repeat itself as $n$
increases to $n+1$ and on an increase we always obtain,
$\Delta(J_{n+1}(f(x)))=\Delta(J_{n}(f(x)))+m$.

######  Theorem 2.6.

The Jaco graph $J_{k}(f(x))$, $k=f((m+c)+1)+1$ is the smallest Jaco graph in
$\\{J_{n}(f(x)):n\in\mathbb{N}\\}$ which has $\Delta(J_{k}(f(x)))=f((m+c)+1)$
with unique Jaconian vertex $v_{(m+c)+1}.$

###### Proof.

We will prove the result through _imbedded_ induction.
Let $c=0$ so consider the linear function $f(x)=mx.$ For $m=1$ let
$f^{\prime}(x)=x.$ The graph $J_{3}(f^{\prime}(x))$ is clearly the smallest
Jaco graph in $\\{J_{n}(f^{\prime}(x)):n\in\mathbb{N}\\}$ for which
$\Delta(J_{3}(f^{\prime}(x)))=(1+0)+1=2$ and
$\mathbb{J}(J_{3}(f^{\prime}(x)))=\\{v_{((1+0)+1)}\\}=\\{v_{2}\\}.$ So the
result holds for $m=1.$

Assume the result holds for $m=\ell,$ and let $f^{\prime\prime}(x)=\ell x.$ So
for the smallest Jaco graph $J_{l}(f^{\prime\prime}(x)),l=\ell(\ell+1)+1$ we
have that $\Delta(J_{l}(f^{\prime\prime}(x)))=\ell(\ell+1)$ and
$\mathbb{J}(J_{l}(f^{\prime\prime}(x)))=\\{v_{(\ell+1)}\\}.$

Now consider the linear function $f^{\prime\prime\prime}(x)=(\ell+1)x.$ In the
Jaco graph $J_{l}(f^{\prime\prime}(x))$ the vertex
$v_{(\ell+1)+1}=v_{(\ell+2)}$ has $d(v_{(\ell+2)})=d(v_{(\ell+1)})-1.$ So in
constructing the Jaco graph $J_{l}(f^{\prime\prime\prime}(x)),$ amongst others
the arc $(v_{1},v_{(m+2)})$ is linked. So at least
$v_{(\ell+1)},v_{(\ell+2)}\in\mathbb{J}(J_{l}(f^{\prime\prime\prime}(x))).$ So
$d(v_{(\ell+2)})=\ell(\ell+1).$ If follows that the minimum number of
additional vertices (smallest Jaco graph) say $t,$ to be added to
$J_{l}(f^{\prime\prime\prime}(x))$ to obtain
$d(v_{(\ell+2)})=(\ell+1)(\ell+2)$ and
$\mathbb{J}(J_{(l+t)}(f^{\prime\prime\prime}(x)))=\\{v_{(\ell+2)}\\}$ in
$J_{(l+t)}(f^{\prime\prime\prime}(x))$ is given by
$t=(\ell+1)(\ell+2)-\ell(\ell+1)=2(\ell+1).$ The number of vertices of
$J_{l}(f^{\prime\prime}(x))$ is given by $\ell(\ell+1)+1.$ Now
$l+t=(\ell(\ell+1)+1)+2(\ell+1)=(\ell+1)(\ell+2)+1.$

Clearly at least
$v_{(\ell+2)}\in\mathbb{J}(J_{k}(f^{\prime\prime\prime}(x))),k=l+t,$ and
$v_{(\ell+1)}\notin\mathbb{J}(J_{k}(f^{\prime\prime\prime}(x)))$ since
$\ell(\ell+1)<(\ell+1)(\ell+2).$ In the construction of the Jaco graph
$J_{l}(f^{\prime\prime\prime}(x)),$ the arc $(v_{1},v_{(\ell+3)})$ was not
linked so $d(v_{(\ell+3)})<d(v_{(\ell+2)})$ in
$J_{l}(f^{\prime\prime\prime}(x)).$ So it follows that
$d(v_{(\ell+3)})<d(v_{(\ell+2)})$ in $J_{k}(f^{\prime\prime\prime}(x)),k=l+t.$
The latter implies that $J(J_{k}(f^{\prime\prime\prime}(x)))$ is the smallest
such Jaco graph and
$\mathbb{J}(J_{k}(f^{\prime\prime\prime}(x)))=\\{v_{(\ell+2)}\\}.$

Hence the result holds for $m=\ell+1$ implying it holds in general for $c=0.$

Now let $c=1,$ and $f(x)=mx+1.$ For $m=1$ let $f^{\prime}(x)=x+1.$ Clearly
$J_{5}(f^{\prime}(x))$ is the smallest Jaco gaph in
$\\{J_{n}(f^{\prime}(x)):n\in\mathbb{N}\\}$ for which
$\Delta(J_{5}(f^{\prime}(x)))=f^{\prime}(2)+1=4$ and
$\mathbb{J}(J_{5}(f^{\prime}(x)))=\\{v_{(2+1)}\\}=\\{v_{3}\\}.$ So the result
holds for $m=1.$

Assume it holds for $m=\ell,$ and let $f^{\prime\prime}(x)=\ell x+1.$ So for
the smallest Jaco graph $J_{l}(f^{\prime\prime}(x)),l=\ell^{2}+2\ell+1$ we
have that $\Delta(J_{l}(f^{\prime\prime}(x)))=\ell(\ell+2)$ and
$\mathbb{J}(J_{l}(f^{\prime\prime}(x)))=\\{v_{(\ell+2)}\\}.$

Now consider the function $f^{\prime\prime\prime}(x)=(\ell+1)x+1.$ In the Jaco
graph $J_{l}(f^{\prime\prime}(x))$ the vertex $v_{(\ell+2)+1}=v_{\ell+3}$ has
$d(v_{\ell+3})=d(v_{\ell+2})-1.$ So in the construction of the Jaco graph
$J_{l}(f^{\prime\prime\prime}(x)),$ amogst others the arc $(v_{1},v_{\ell+3})$
is linked. So at least
$v_{(\ell+2)},v_{(\ell+3)}\in\mathbb{J}(J_{l}(f^{\prime\prime\prime}(x))).$ So
$d(v_{(\ell+3)})=\ell(\ell+2).$ If follows that the minimum number of
additional vertices (smallest Jaco graph) say $t,$ to be added to
$J_{l}(f^{\prime\prime\prime}(x))$ to obtain
$d(v_{(\ell+3)})=(\ell+2)(\ell+3)$ and
$\mathbb{J}(J_{(l+t)}(f^{\prime\prime\prime}(x)))=\\{v_{(\ell+3)}\\}$ in
$J_{(l+t)}(f^{\prime\prime\prime}(x))$ is given by
$t=(\ell+2)(\ell+3)-\ell(\ell+2)=2(\ell+2).$ The number of vertices of
$J_{l}(f^{\prime\prime}(x))$ is given by $(\ell+1)(\ell+2)+1.$ Now
$l+t=((\ell+1)(\ell+2)+1)+2((\ell+1)+1)=(\ell+2)(\ell+3)+1.$

Clearly at least
$v_{(\ell+3)}\in\mathbb{J}(J_{k}(f^{\prime\prime\prime}(x))),k=l+t,$ and
$v_{(\ell+2)}\notin\mathbb{J}(J_{k}(f^{\prime\prime\prime}(x)))$ since
$(\ell+1)(\ell+2)<(\ell+2)(\ell+3).$ In the construction of the Jaco graph
$J_{l}(f^{\prime\prime\prime}(x)),$ the arc $(v_{1},v_{(\ell+4)})$ was not
linked so $d(v_{(\ell+4)})<d(v_{(\ell+3)})$ in
$J_{l}(f^{\prime\prime\prime}(x)).$ So it follows that
$d(v_{(\ell+4)})<d(v_{(\ell+3)})$ in $J_{k}(f^{\prime\prime\prime}(x)),k=l+t.$
The latter implies that $J(J_{k}(f^{\prime\prime\prime}(x)))$ is the smallest
such Jaco graph and
$\mathbb{J}(J_{k}(f^{\prime\prime\prime}(x)))=\\{v_{(\ell+3)}\\}.$

Hence the result holds for $m=\ell+1$ implying it holds in general for $c=1.$

Now assume the result holds for $1\leq m\leq\ell_{1}$ and $0\leq c\leq
c_{\ell}$. This means that for $f^{\prime}(x)=\ell_{1}x+c_{\ell}$ the smallest
Jaco graph $J_{l}(f^{\prime}(x))$ has
$\Delta(J_{l}(f^{\prime}(x)))=f^{\prime}((\ell_{1}+c_{\ell})+1)=\ell_{1}(\ell_{1}+c_{\ell})+1)+c_{\ell}.$
and $\mathbb{J})J_{l}(f^{\prime}(x)))=\\{v_{(\ell_{1}+c_{\ell})+1}\\}.$ Now
consider the linear function $f^{\prime\prime}(x)=(\ell_{1}+1)x+(c_{\ell}+1).$

In the Jaco graph $J_{l}(f^{\prime}(x))$ the vertex
$v_{(\ell+c_{\ell}+2)+1}=v_{\ell+c_{\ell}+3}$ has
$d(v_{\ell+c_{\ell}+3})=d(v_{\ell+c_{\ell}+2})-1.$ So in the construction of
the Jaco graph $J_{l}(f^{\prime\prime}(x)),$ amogst others the arc
$(v_{1},v_{\ell+c_{\ell}+3})$ is linked. So at least
$v_{(\ell+c_{\ell}+2)},v_{(\ell+c_{\ell}+3)}\in\mathbb{J}(J_{l}(f^{\prime\prime}(x))).$
So $d(v_{(\ell+c_{\ell}+3)})=(\ell+c_{\ell})(\ell+c_{\ell}+2).$ If follows
that the minimum number of additional vertices (smallest Jaco graph) say $t,$
to be added to $J_{l}(f^{\prime\prime}(x))$ to obtain
$d(v_{(\ell+c_{\ell}+3)})=(\ell+c_{\ell}+2)(\ell+c_{\ell}+3)$ and
$\mathbb{J}(J_{(l+t)}(f^{\prime\prime}(x)))=\\{v_{(\ell+c_{\ell}+3)}\\}$ in
$J_{(l+t)}(f^{\prime\prime}(x))$ is given by
$t=(\ell+c_{\ell}+2)(\ell+c_{\ell}+3)-(\ell+c_{\ell})(\ell+c_{\ell}+2)=2(\ell+c_{\ell}+2).$
The number of vertices of $J_{l}(f^{\prime}(x))$ is given by
$(\ell+c_{\ell}+1)(\ell+c_{\ell}+2)+1.$ Now
$l+t=((\ell+c_{\ell}+1)(\ell+c_{\ell}+2)+1)+2((\ell+c_{\ell}+1)+1)=(\ell+c_{\ell}+2)(\ell+c_{\ell}+3)+1.$

Clearly at least
$v_{(\ell+c_{\ell}+3)}\in\mathbb{J}(J_{k}(f^{\prime\prime}(x))),k=l+t,$ and
$v_{(\ell+c_{\ell}+2)}\notin\mathbb{J}(J_{k}(f^{\prime\prime}(x)))$ since
$(\ell+c_{\ell}+1)(\ell+c_{\ell}+2)<(\ell+c_{\ell}+2)(\ell+c_{\ell}+3).$ In
the construction of the Jaco graph $J_{l}(f^{\prime\prime}(x)),$ the arc
$(v_{1},v_{(\ell=c_{\ell}+4)})$ was not linked so
$d(v_{(\ell+c_{\ell}+4)})<d(v_{(\ell+c_{\ell}+3)})$ in
$J_{l}(f^{\prime\prime}(x)).$ So it follows that
$d(v_{(\ell+c_{\ell}+4)})<d(v_{(\ell+c_{\ell}+3)})$ in
$J_{k}(f^{\prime\prime}(x)),k=l+t.$ The latter implies that
$J(J_{k}(f^{\prime\prime}(x)))$ is the smallest such Jaco graph and
$\mathbb{J}(J_{k}(f^{\prime\prime}(x)))=\\{v_{(\ell+c_{\ell}+3)}\\}.$

Hence the result holds for $m=\ell_{1}+1$ and $c_{\ell}+1$ implying it holds
in general for $f(x)=mx+c.$ ∎

##  3 Number of Arcs of the Finite Jaco Graphs
$\\{J_{n}(f(x)):f(x)=mx+c;x,m\in\mathbb{N}$ and $c\in\mathbb{N}_{0}\\}$

Note, in [6,7] it was thought that Theorem 3.7 combined with Binet’s formula
perhaps amounts to a closed formula for $d^{+}(v_{n}).$ It is hoped that as a
generalised case, a closed formula can be found for the number of arcs of a
finite Jaco graph $J_{n}(f(x)).$ Theorem 3.8 provides a result for a subset of
the family of Jaco graphs $J_{n}(f(x)).$ The algorithms discussed in Ahlbach
et al.[1] suggest that a general closed formula might not be found. First we
present results for $c=0$ hence for $f(x)=mx.$

######  Proposition 3.1.

The number of arcs of a Jaco graph $J_{\ell}(mx)=\frac{1}{2}\ell(\ell-1)$ if
$\ell\leq m+1.$

###### Proof.

If $\ell=m+1$ then, $((m+1)+1).1-d^{-}(v_{1})>(m+1)$ so from definition 2.1 it
follows that the arcs $(v_{1},v_{i}),i=2,3,...,(m+1)$ exist. It then follows
that all arcs $(v_{i},v_{j}),i<j$ exist. So the underlying graph
$J^{*}_{m+1}(m)$ is the complete graph $K_{m+1}$ hence,
$\epsilon(J_{m+1}(m))=\frac{1}{2}m(m+1)=\frac{1}{2}\ell(\ell-1).$ The result
follows similarly for $\ell<m+1.$ ∎

######  Theorem 3.2.

If for the Jaco graph $J_{n}(mx),$ we have $\Delta(J_{n}(mx))=k,$ then
$\epsilon(J_{n}(mx))=\epsilon(\mathbb{H}(J_{n}(mx)))+\sum\limits_{i=1}^{k}d^{+}(v_{i}).$

###### Proof.

For $n=1,$ $d^{+}(v_{1})=0$ and $J_{1}(mx)$ is the arcless graph on vertex
$v_{1}$ whilst $\mathbb{H}(J_{1}(mx)),$ is an empty graph so
$A(\mathbb{H}(J_{1}(mx)))=\emptyset,$ implying
$\epsilon(\mathbb{H}(J_{1}(mx)))=0.$ Thus the result holds.

For $n=2,$ the Jaco graph $J_{2}(mx)$ has the prime Jaconian vertex $v_{1}$
and $d^{+}(v_{1})=1.$ $\mathbb{H}(J_{2}(mx))$ is the null graph on vertex
$v_{2}$ so $A(\mathbb{H}(J_{2}(a)))=\emptyset,$ implying
$\epsilon(\mathbb{H}(J_{2}(mx)))=0.$ Thus the result holds.

Now assume it holds for all vertices $v_{i},$ $i\leq k-1.$ Thus vertex $v_{k}$
has attained its in-degree $d^{-}(v_{k}).$ To attain
$d(v_{k})=\Delta(J_{n}(mx)),$ exactly
$\Delta(J_{n}(mx))-d^{-}(v_{k})=d^{+}(v_{k})$ arcs can be linked additionally.
So the result holds for vertices $v_{1},v_{2},v_{3},\cdots,v_{k}.$

Clearly we also have $A(\mathbb{H}(J_{n}(mx)))\subset A(J_{n}(mx)).$ Hence,
$\epsilon(J_{n}(mx))=\epsilon(\mathbb{H}(J_{n}(mx)))+d^{+}(v_{1})+d^{+}(v_{2})+d^{+}(v_{3})+\cdots+d^{+}(v_{k}).$
Since it is known that
$\epsilon(\mathbb{H}(J_{n}(mx)))=1+2+3+\cdots+(n-\Delta(J_{n}(mx))-1)$ the
result can be written as
$\epsilon(J_{n}(mx))=\frac{1}{2}(n-k)(n-k-1)+\sum\limits_{i=1}^{k}d^{+}(v_{i}).$
∎

######  Corollary 3.3.

The number of arcs of a Jaco graph $J_{n}(mx)$ having vertex $v_{i}$ as the
prime Jaconian vertex, can also be expressed recursively as

$\epsilon(J_{n+1}(mx))=\begin{cases}\epsilon(J_{n}(mx))-i+n&\text{if
$d(v_{i})=mi$}\\\ \epsilon(J_{n}(mx))-i+(n+1)&\text{if $d(v_{i})<mi$}\\\
\end{cases}$

###### Proof.

Consider the Jaco graph $J_{n}(mx)$ having vertex $v_{i}$ as the Jaconian
vertex.

Case1: If $d(v_{i})=mi$ and the vertex $v_{(n+1)}$ is added to construct
$J_{(n+1)}(f(x))$ only the arcs $(v_{(i+1)},v_{(n+1)}),....(v_{n},v_{(n+1)})$
can be linked additionally. This amounts to $(n-i)$ arcs.

Case 2: If $d(v_{i})<mi$ and the vertex $v_{(n+1)}$ is added to construct
$J_{(n+1)}(mx)$ only the arcs
$(v_{i},v_{(n+1)}),(v_{(i+1)},v_{(n+1)}),....(v_{n},v_{(n+1)})$ can be linked
additionally. This amounts to $(n-i+1)$ arcs. ∎

######  Lemma 3.4.

(Also see [7].) We find for $m=1$ and the series
$(a_{n})_{n\in\mathbb{N}_{0}}$ defined by

$a_{0}=0,a_{1}=1,a_{n\geq 2}=\min\\{k<n:k+a_{k}\geq n\\},$

that Lemma 1.1 changes to:
(a) $d^{+}(v_{n})+d^{-}(v_{n})=n.$
(b) $d^{-}(v_{n+1})\in\\{d^{-}(v_{n}),\,d^{-}(v_{n})+1\\}.$
(c) If $(v_{i},v_{k})\in A(J_{\infty}(x))$ and $i<j<k,$ then $(v_{j},v_{k})\in
A(J_{\infty}(x)).$
(d) $d^{+}(v_{n})=a_{n},$ $n\geq 2.$

######  Corollary 3.5.

Note that $(a))$ and $(c)$ above entail that
$d^{+}(v_{n+1})=n+1-d^{-}(v_{n+1})\in\\{n-d^{-}(v_{n}),n-d^{-}(v_{n})+1\\}$
and that $(d)$ then implies tat the series $(a_{n})$ is well defined and
ascending, more specifically, $a_{n+1}\in\\{a_{n},a_{n}+1\\},$
$(n\in\mathbb{N}_{0}).$

######  Lemma 3.6.

Let $i\in\mathbb{N}.$ Then
$d^{+}(v_{i+d^{+}(v_{i})})=i=d^{+}(v_{i+d^{+}(v_{i+d^{+}(v_{i-1})})}).$

###### Proof.

let $i+d^{+}(v_{i})=k.$ Certainly, $i+d^{+}(v_{i})\geq k,$ so
$d^{+}(v_{k})\leq i.$ From Lemma 3.4 it follows that $i-1+d^{+}(v_{i-1})\leq
i-1+d^{+}(v_{i})<i+d^{+}(v_{i})$ so $d^{+}(v_{k})\geq i.$ Let
$\ell=i+d^{+}(v_{i-1}).$ Since $d^{+}(v_{i})\geq d^{+}(v_{i-1})$ we have,
$d^{+}(v_{\ell})\leq i$ and since, $i-1+d^{+}(v_{i-1})<\ell$ we have,
$d^{+}(v_{\ell})=i.$ ∎

The next theorem with proof is repeated here. It appears in [6, 7] which are
announcement papers only. Applicable reading related to Fibonacci numbers and
Zeckendorf representations is found in [5, 9].

######  Theorem 3.7.

(Bettina’s Theorem)(Also see: [6, 7]). Let
$\mathbb{F}=\\{f_{0},f_{1},f_{2},...\\}$ be the set of Fibonacci numbers and
let $n=f_{i_{1}}+f_{i_{2}}+...+f_{i_{r}},n\in\mathbb{N}$ be the Zeckendorf
representation of $n.$ Then

$d^{+}(v_{n})=f_{i_{1}-1}+f_{i_{2}-1}+...+f_{i_{r}-1}.$

###### Proof.

Through induction we have that first of all, $1=f_{2}$ and
$d^{+}(v_{1})=1=f_{1}.$ Let $2\leq n=f_{i_{1}}+f_{i_{2}}+...+f_{i_{r}}$ and
let $k=f_{i_{1}-1}+f_{i_{2}-1}+...+f_{i_{r}-1}.$ If $i_{r}\geq 3,$ then
$k=f_{i_{1}-1}+f_{i_{2}-1}+...+f_{i_{r}-1}$ is the Zeckendorf representation
of $k$, such that induction yields
$d^{+}(v_{k})=k=f_{i_{1}-2}+f_{i_{2}-2}+...+f_{i_{r}-2}.$ Since
$k+d^{+}(v_{k})=f_{i_{1}-1}+f_{i_{1}-2}+f_{i_{2}-1}+f{i_{2}-2}+...f_{i_{r}-1}+f_{i_{r}-2}=f_{i_{1}}+f_{i_{2}}+...f_{i_{r}}=n,$
read with Lemma 3.6 yields $d^{+}(v_{n})=k.$

Finally consider $n=f_{i_{1}}+f_{i_{2}}+...+f_{i_{r}},i_{r}=2.$ Note that
$n>1$ implies that $i_{r-1}\geq 4$ and that the Zeckendorf representation of
$n-1$ given by $n-1=f_{i_{1}}+f_{i_{2}}+...+f_{i_{r-1}}.$ Let
$k=d^{+}(v_{n-1}).$ Through induction we have that,
$k=f_{i_{1}-1}+f_{i_{2}-1}+...+f_{i_{r-1}-1},$ and since $i_{r-1}\leq 4,$ this
is the Zeckendorf representation of $k.$ Accordingly,
$d(v_{k})=f_{i_{1}-2}+f_{i_{2}-2}+...+f_{i_{r-1}-2},$ and
$k+d^{+}(v_{k})=f_{i_{1}-1}+f_{i_{1}-2}+f_{i_{2}-1}+f{i_{2}-2}+...f_{i_{r-1}-1}+f_{i_{r-1}-2}=n-1.$
It follows that $d^{+}(v_{n})>k=d^{+}(v_{n-1}).$ From Corollary 3.5 it follows
that
$d^{+}(v_{n})=k+1=(f_{i_{1}-1}+f_{i_{2}-1}+...+f_{i_{r-1}-1})+f_{1}=f_{i_{1}-1}+f_{i_{2}-1}+...+f_{i_{r}-1}.$
∎

Since $d^{-}(v_{n})=n-d^{+}(v_{n})$, the number of edges is also given by
$\epsilon(J_{n}(1))=\frac{1}{2}n(n+1)-\sum\limits^{n}_{i=1}d^{+}(v_{i}).$
Furthermore, for $n\geq 2$ we have $d^{+}(v_{1})=1$, so we rather consider
$\epsilon(J_{n}(1))=(\frac{1}{2}(n(n+1)-1)-\sum\limits^{n}_{i=2}d^{+}(v_{i}).$
Bettina’s theorem can be applied to the last term to determine the number of
arcs of $J_{n}(x).$

Illustration 2. For the Jaco Graph $J_{15}(x)$ we have;
$\epsilon(J_{15}(1))=\frac{1}{2}.15.(15+1)-1-\sum\limits^{15}_{i=2}=119-\sum\limits^{15}_{i=2}d^{+}(v_{i}).$

Now,
$f_{2}=1,f_{3}=2,f_{4}=3,f_{4}+f_{2}=4,f_{5}=5,f_{5}+f_{2}=6,f_{5}+f_{3}=7,f_{6}=8,f_{6}+f_{2}=9,f_{6}+f_{3}=10,f_{6}+f_{4}=11,f_{6}+f_{4}+f_{2}=12,f_{7}=13,f_{7}+f_{2}=14,$
and $f_{7}+f_{3}=15.$

From Bettina’s Theorem it follows that;
$\sum\limits^{15}_{i=2}d^{+}(v_{i})=f_{2}+f_{3}+(f_{3}+f_{1})+f_{4}+(f_{4}+f_{1})+(f_{4}+f_{2})+f_{5}+(f_{5}+f_{1})+(f_{5}+f_{2})+(f_{5}+f_{3})+(f_{5}+f_{3}+f_{1})+f_{6}+(f_{6}+f_{1})+(f_{6}+f_{2})=5f_{1}+4f_{2}+4f_{3}+3f_{4}+5f_{5}+3f_{6}=f_{1}+5f_{3}+5f_{5}+3f_{7}=75.$

So, $\epsilon(J_{15}(1))=119-75=44.$

Now we present a result for a special case in respect of $f(x)=mx+c.$

######  Theorem 3.8.

For the Jaco graph $J_{f(f(1)+1)+1)+1}(f(x))$ we have that:
$\epsilon(J_{f(f(1)+1)+1)+1}(f(x)))=\epsilon(K_{f(1)+1})+\epsilon(K_{f(f(1)+1))-f(1)})+\frac{1}{2}mf(1)\cdot(f(1)-1),$
alternatively,
$\epsilon(J_{m^{2}+m(c+1)+2}(f(x)))=\epsilon(K_{(m+c)+1})+\epsilon(K_{m^{2}+m(c-1)-c+2})+\frac{1}{2}m(m+c)\cdot((m+c)-1).$

###### Proof.

Clearly the Jaco graph $J_{f(1)+1}(f(x))$ is the complete graph
$K_{f(1)+1}=K_{m+c+1},$ so the first term including the first alternative
term, follows. Clearly the induced subgraph $\langle v_{i}:f(1)+1\leq i\leq
f(f(1)+1)+1\rangle$ is the complete graph
$K_{(f(f(1)+1)+1)-(f(1)+1))}=K_{m^{2}+m(c-1)-c+2},$ so the second term
including the second alternative term, follows.

Consider the graph $J^{\prime}$ to be the graph obtained by appending the two
complete graphs above at the common vertex $v_{f(1)+1}.$ To obtain the Jaco
graph $J_{f(f(1)+1)+1)+1}(f(x))$ from graph $J^{\prime}$ we have to add all
defined arcs from vertices $v_{j}\in\\{v_{i}:2\leq i\leq f(1)\\}$ to vertices
$v_{k}\in\\{v_{\ell}:f(1)+2\leq\ell\leq f(f(1)+1)\\}.$ Choose any such vertex
$v_{j}$ and we have $d_{J^{\prime}}(v_{j})=f(1)=m+c.$ Relabel the vertex
$v_{j}$ to carry index $j-1$ and denote the vertex $v^{*}_{j-1}.$ So now we
have that $d_{J^{\prime}}(v^{*}_{j-1})=m+c.$ Since
$d_{J_{f(f(1)+1)+1)+1}(f(x))}(v_{j})=mj+c,$ the additional $mj+c-(m+c)=m(j-1)$
arcs must be added.

Hence, $\sum\limits_{i=2-1}^{m+c-1}mi=m\cdot\sum\limits_{i=2-1}^{m+c-1}i$ arcs
are required. This simplifies to
$m\cdot\sum\limits_{i=1}^{m+c-1}i=m\cdot(\frac{1}{2}(m+c)(m+c-1)$ arcs. By
this the result is settled. ∎

###  3.1 Linear Function Corresponding to a Linear Jaco Graph

It is noted that if for a sufficiently large linear Jaco Graph $J_{n}(f(x))$
we have two vertices $v_{i},v_{j}$ for which $d(v_{i})=f(i)$ and
$d(v_{j})=f(j)$ then the linear function $f(x)$ can be derived by solving the
simultaneous equations:

$mi+c=d(v_{i})$

$mj+c=d(v_{j}).$

The smallest linear Jaco graph for which this is possible is for
$J_{f(2)+1}(f(x))$ hence, knowing that $d(v_{2})=f(2)$ in the given linear
Jaco graph.

######  Proposition 3.9.

If for a linear Jaco graph we have that $d(v_{i})=f(i)$ and
$d(v_{i+1})=f(i+1)$ then for maximum $i^{\prime},j^{\prime}$ for which the
arcs $(v_{i},v_{i^{\prime}}),(v_{i+1},v_{j^{\prime}})$ exist, we have
$j^{\prime}-i^{\prime}\in\\{m,m+1\\}.$

###### Proof.

Let $d(v_{i})=f(i)$ and $d(v_{i+1})=f(i+1)$ in a sufficiently large linear
Jaco graph $J_{n}(f(x)).$ Since $d(v_{i+1})-d(v_{i})=m(i+1)+c-mi-c=m$ and from
Lemma 1.1(b) we have $d^{-}(v_{i+1})\in\\{d^{-}(v_{i}),d^{-}(v_{i})+1\\}$, the
result follows. ∎

Each positive integer $k$ can be written as $k+1$ sums of non-negative
integers $m+c$, $m\geq 0,c\geq 0.$ If in definition 1.1 we relax the lower
limit on $m$ and allow $m\geq 0$ we say for a given $k$ that the linear Jaco
graphs corresponding to the functions $f_{i}(x)=m_{i}x+c_{i}$, $m_{i}+c_{i}=k$
and $1\leq i\leq k+1,$ are $f$-related Jaco graphs.

For $m=0$ and $c\geq 0$ we have two special classes of disconnected linear
Jaco graphs. For $c=0$ the Jaco graph $J_{n}(0)$ is a null graph (_edgeless
graph_) on $n$ vertices. For $c=k>0$, the Jaco graph
$J_{n}(k)=\bigcup\limits_{\lfloor\frac{n}{k+1}\rfloor-copies}K_{k+1}\bigcup
K_{n-(k+1)\cdot\lfloor\frac{n}{k+1}\rfloor}.$

Illustration 3. Figure 2 depicts the linear Jaco graph $J_{15}(3)=K_{4}\bigcup
K_{4}\bigcup K_{4}\bigcup K_{3}.$

Figure 2:

We note that a complete graph $K_{n}$ is a linear Jaco graph to any linear
function $f(x)=mx+c$ if $n\leq m+c+1.$ And, if $K_{n}$ is a $f$-related linear
Jaco graph, the complete graph corresponds to any of the $m+c+1$ defined
linear functions. It implies that we need at least a two-component subgraph of
complete graphs say $K_{s}\bigcup K_{t}$ to derive the unique linear function
$f(x)=k-1,$ $k=max\\{s,t\\}.$

##  4 Conclusion

Thus far all studies of Jaco graphs were indeed on linear Jaco graphs. We
largely generalised the results announced in [6, 7]. Also note that the Jaco
graphs $J_{n}(1)$ and $J_{n}(a)$ as discussed in [6, 7] has a slightly
different meaning to that defined in this paper. This might make comparative
reading somewhat confusing. The generalisation suggests uniform notation.
Amongst the many open problems that exist within the family of Jaco graphs the
authors view, finding a closed formula for the number of arcs (edges) of a
Jaco graph the most challenging and interesting. Perhaps Theorem 3.8 lays the
foundation to further seek such closed formula.

It is proposed that the generalisation of the concepts to polynomial Jaco
graphs $J_{n}(f(x))$ where $f(x)=\sum\limits_{i=1}^{t}a_{i}x^{i}+c,$
$a_{i},x\in\mathbb{N}$ and $c\in\mathbb{N}_{0},$ will be worthy to study.
Definition 1.1 will have to change to define the orientation of edges
resulting from $f(x)<0.$ Also, given a sufficiently large polynomial Jaco
graph, deriving the polynomial function can be formalised.

References

$[1]$ C. Ahlbach, j. Usatine, N. Pippenger, _Efficient Algorithms for
Zerckendorf Arithmetic,_ Fibonacci Quarterly, Vol 51, No. 13, (2013): pp
249-255.
$[2]$ J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan
Press, London, (1976).
$[3]$ G. Chartrand and L. Lesniak, Graphs and Digraphs, CRC Press, 2000.
$[4]$ J.T. Gross and J. Yellen, Graph Theory and its Applications, CRC Press,
2006.
$[5]$ D. Kalman and R.Mena, _The Fibonacci Number - Exposed,_ Mathematics
Magazine, Vol 76, No. 3, (2003): pp 167-181.
$[6]$ J. Kok, P. Fisher, B. Wilkens, M. Mabula, V. Mukungunugwa,
_Characteristics of Finite Jaco Graphs, $J_{n}(1),n\in\mathbb{N}$_, arXiv:
1404.0484v1 [math.CO], 2 April 2014.
$[7]$ J. Kok, P. Fisher, B. Wilkens, M. Mabula, V.
Mukungunugwa,_Characteristics of Jaco Graphs, $J_{\infty}(a),a\in\mathbb{N}$_,
arXiv: 1404.1714v1 [math.CO], 7 April 2014.
$[8]$ D.B. West, Introduction to Graph Theory, Pearson Education Incorporated,
2001. $[9]$ E. Zeckendorf, _Représentation des nombres naturels par une somme
de nombres de Fibonacci ou de nombres de Lucas,_ Bulletin de la Société Royale
des Sciences de Liège, Vol 41, (1972): pp 179-182.

[Remark: The concept of Jaco Graphs followed from a dream during the night of
10/11 January 2013 which was the first dream Kokkie (first author) could
recall about his daddy after his daddy passed away in the peaceful morning
hours of 24 May 2012, shortly before the awakening of Bob Dylan, celebrating
Dylan’s 71st birthday]