Total Irregularity and $f_{t}$-Irregularity of Linear Jaco Graphs

Johan Kok

Tshwane Metropolitan Police Department

City of Tshwane, Republic of South Africa

<EMAIL_ADDRESS>
###### Abstract

Abdo and Dimitrov defined the total irregularity of a simple undirected graph
$G$ to be $irr_{t}(G)=\frac{1}{2}\sum\limits_{u,v\in V(G)}|d(u)-d(v)|.$ In
this study we allocate the _Fibonacci weight_ , $f_{i}$ to a vertex $v_{j}$ of
a simple connected graph $G,$ if and only if $d(v_{j})=i$ and define the
_total fibonaccian irregularity_ or $f_{t}$-irregularity as
$firr_{t}(G)=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|f_{i}-f_{j}|.$ The
concept of an _edge-joint_ denoted $G\rightsquigarrow_{vu}H$ is also
introduced This paper presents results for the undirected underlying graph
$J^{*}_{n}(x)$ of a Jaco Graphs, $J_{n}(x),$ $n,x\in\mathbb{N}.$

Keywords: Total irregularity, Fibonacci weight, Total $f$-irregularity,
Fibonaccian irregularity, Jaco graphs, Jaconian vertices, Fisher algorithm,
Edge-joint.

AMS Classification Numbers: 11B39, 05C07, 05C20, 05C22, 05C75

##  1 Introduction

For a general reference to notation and concepts of graph theory see [3].
Unless mentioned otherwise, only simple undirected graphs or the underlying
graph of directed graphs will be considered. Abdo and Dimitrov [1, 2] defined
total irregularity of a simple undirected graph $G$ to be
$irr_{t}(G)=\frac{1}{2}\sum\limits_{u,v\in V(G)}|d(u)-d(v)|.$ If the vertices
of a simple undirected graph $G$ on $n$ vertices are labeled
$v_{i},i=1,2,3,\dots,n$ then the definition may be
$irr_{t}(G)=\frac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|d(v_{i})-d(v_{j})|=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|$
or $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|.$ For a
simple graph on a singular vertex (_1-empty_ graph), we define $irr_{t}(G)=0$
.

A new notion of vertex labeling is inherent to the definition of total
irregularity. That is, let $g:V(G)\mapsto\mathbb{N}$ with $g(v)=d_{G}(v),$
$\forall v\in V(G).$ In Section 2 the total irregularity of finite linear Jaco
graphs is discussed. This is followed by the introduction of _total
fibonaccian irregularity_ of graphs. This new irregularity or vertex labeling
is applied to finite linear Jaco graphs in Section 3.

The content is fairly straight forward in that it demonstrates _constructive
counting technique_ only. The real contribution is that the approach
demonstrates the graphical embodiment of mainly, a number theoretical problem
stemming from well-defined graphs in terms of their structure. Essentially, we
see that total irregularity presents a sum of differences between all pairs of
natural numbers in a subset $X\subset\mathbb{N}$ for $X$ having an even number
of odd numbers. Similarly, total fibonaccian irregularity presents a sum of
differences between all pairs of fibonacci numbers in a subset
$X\subset\mathbb{F}$ for $X$ having an even number of fibonacci numbers with
odd subscripts.

##  2 Total Irregularity of Finite Linear Jaco Graphs

The concept of linear Jaco graphs was introduced Kok et al. [4, 5]. In the
initial studies the concepts of _order 1_ and _order $a$_ Jaco graphs, denoted
$J_{n}(1)$, $J_{n}(a)$ respectively, were reported on. In a more recent study
(see [5]) a unifying definition was adopted and the generalised family called,
linear Jaco graphs was defined.A particular family of finite directed graphs
called Jaco Graphs and denoted by $J_{n}(x),$ $n,x\in\mathbb{N}$ are derived
from a particular well-defined infinite directed graph, called the _x_ -root
digraph. The _x_ -root digraph has four fundamental properties which are;
$V(J_{\infty}(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 $k$ is $d(v_{k})=k.$ The family of finite directed graphs are those
limited to $n\in\mathbb{N}$ vertices by lobbing off all vertices (and arcs)
$v_{t},t>n.$ Hence, trivially we have $d(v_{i})\leq i$ for $i\in\mathbb{N}.$
When the context is clear we refer to the Jaco graph $J_{n}(x)$, the
underlying Jaco graph $J^{*}_{n}(x)$, arcs $A(J_{n}(x))$ and edges
$E(J_{n}(x))$, the degree
$d_{J_{n}(x)}(v_{i})=d^{+}_{J_{n}(x)}(v_{i})+d^{-}_{J_{n}(x)}(v_{i})=d^{+}_{J^{*}_{n}(x)}(v_{i})+d^{-}_{J^{*}_{n}(x)}(v_{i})=d(v_{i}),$
interchangeably.

######  Definition 2.1.

$[6]$ The infinite Jaco Graph $J_{\infty}(x)$ is defined by
$V(J_{\infty}(x))=\\{v_{i}:i\in\mathbb{N}\\}$,
$A(J_{\infty}(x))\subseteq\\{(v_{i},v_{j}):i,j\in\mathbb{N},i<j\\}$ and
$(v_{i},v_{j})\in A(J_{\infty}(x))$ if and only if $2i-d^{-}(v_{i})\geq j.$

######  Definition 2.2.

$[6]$ The family of finite Jaco Graphs are defined by $\\{J_{n}(x)\subseteq
J_{\infty}(x):n,x\in\mathbb{N}\\}.$ A member of the family is referred to as
the Jaco Graph, $J_{n}(x).$

For illustration the adapted table below follows from the Fisher algorithm
$[4]$ for $J_{n}(x),$ $n,x\in\mathbb{N},$ $n\leq 12.$ The degree sequence of
$J^{*}_{n}(x)$ is denoted $\mathbb{D}(J^{*}_{n}(x)).$ Note that for the
underlying graphs $J^{*}_{n}(x),$ the values $irr_{t}(J^{*}_{n}(x))$ have been
calculated manually, as it is not provided for in the Fisher algorithm.

Table 1.
$i\in{\mathbb{N}}$ $d^{-}(v_{i})$ $d^{+}(v_{i})=i-d^{-}(v_{i})$
$\mathbb{D}(J^{*}_{i}(x))$ $irr_{t}(J^{*}_{i}(x))$ 1 0 1 (0) 0 2 1 1 (1, 1) 0
3 1 2 (1, 2, 1) 2 4 1 3 (1, 2, 2, 1) 4 5 2 3 (1, 2, 3, 2, 2) 8 6 2 4 (1, 2, 3,
3, 3, 2) 14 7 3 4 (1, 2, 3, 4, 4, 3, 3) 26 8 3 5 (1, 2, 3, 4, 5, 4, 4, 3) 42 9
3 6 (1, 2, 3, 4, 5, 5, 5, 4, 3) 60 10 4 6 (1, 2, 3, 4, 5, 6, 6, 5, 4, 4) 86 11
4 7 (1, 2, 3, 4, 5, 6, 7, 6, 5, 5, 4) 116 12 4 8 (1, 2, 3, 4, 5, 6, 7, 7, 6,
6, 5, 4) 149

Note that the Fisher Algorithm determines $d^{+}(v_{i})$ on the assumtion that
the Jaco Graph is always sufficiently large, so at least $J_{n}(x),n\geq
i+d^{+}(v_{i}).$ For a smaller graph the degree of vertex $v_{i}$ is given by
$d(v_{i})=d^{-}(v_{i})+(n-i).$ In $[4,5],$ Bettina’s theorem describes an
arguably, closed formula to determine $d^{+}(v_{i})$. Since
$d^{-}(v_{i})=n-d^{+}(v_{i})$ it is then easy to determine $d(v_{i})$ in a
smaller graph $J_{n}(1),n<i+d^{+}(v_{i}).$

The next result presents a _partially_ recursive formula to determine
$irr_{t}(J_{n+1}(x))$ if $irr_{t}(J_{n}(x)),\\\ n\geq 1$ is known.

######  Theorem 2.1.

Consider the underlying Jaco Graph, $J^{*}_{n}(x),$ $n,x\in\mathbb{N}$ with
$\Delta(J^{*}_{n}(x))=k$ and $irr_{t}(J^{*}_{n}(x))$ known. Let $d(v_{i}),$
$d^{*}(v_{i})$ denote the degree of vertex $v_{i}$ in $J^{*}_{n}(x)$ and
$J^{*}_{n+1}(x)$, respectively. Then for the underlying Jaco graph
$J^{*}_{n+1}(x)$ we have that:

$irr_{t}(J^{*}_{n+1}(x))=irr_{t}(J^{*}_{n}(x))+\sum\limits_{i=1}^{\ell_{1}}i-\sum\limits_{i=1}^{\ell_{2}}i+\sum\limits_{i=1}^{n}|(n-k)-d^{*}(v_{i})|,$

with $\ell_{1}$ the number of vertices $v_{i}$ with $d(v_{i})\leq
d(v_{k+j}),j\in\\{1,2,\dots,n-k\\},$ and $\ell_{2}$ the number of vertices
$v_{i}$ with $d(v_{i})>d(v_{k+j}),j\in\\{1,2,\dots,n-k\\}.$

###### Proof.

Let $J^{*}_{n}(x)$ have the prime Jaconian vertex, $v_{k},$ hence
$d(v_{k})=\Delta(J^{*}_{n}(x))$ as defined in $[4].$ It is also true that
$d(v_{k})=\Delta(J^{*}_{n}(x))=d^{*}(v_{k}).$ By adding vertex $v_{n+1}$ to
construct $J_{n+1}(x),$ the vertex $v_{n+1}$ obtains degree,
$d^{*}(v_{n+1})=n-k.$ Each vertex $v_{k+j},j=1,2,\dots,n-k$ obtains an
additional edge, $v_{k+j}v_{n+1}$ as well.

So clearly $d^{*}(v_{k+j})=d(v_{k+j})+1$ for $j=1,2,\dots,n-k.$ It implies
that $|d^{*}(v_{k+1})-d(v_{i})_{i\leq k}|=\\\ \\\ |d(v_{k+1})-d(v_{i})_{i\leq
k}|+1$ iff $d(v_{i})_{i\leq k}\leq d(v_{k+1}).$ It follow that for the cases
$d(v_{i})_{i\leq k}>d(v_{k+1}),$

we have $|d^{*}(v_{k+1})-d(v_{i})_{i\leq k}|=|d(v_{k+1})-d(v_{i})_{i\leq
k}|-1.$ The ”split-result” follows similarly for
$|d^{*}(v_{k+j})-d(v_{i})_{i\leq k}|,j=2,3,\dots,n-k.$ Therefore the terms,
$+\sum\limits_{i=1}^{\ell_{1}}i-\sum\limits_{i=1}^{\ell_{2}}i$ follow easily.

The terms,
$+\sum\limits_{i=1}^{k}|(n-k)-d(v_{i})|+\sum\limits_{i=k+1}^{n}|(n-k)-d^{*}(v_{i})|$
follow directly from the definition of _total irregularity_ and since it is
true that $d(v_{i})=d^{*}(v_{i})\forall i\leq k,$ we have that:

$\sum\limits_{i=1}^{k}|(n-k)-d(v_{i})|+\sum\limits_{i=k+1}^{n}|(n-k)-d^{*}(v_{i})|=\sum\limits_{i=1}^{n}|(n-k)-d^{*}(v_{i})|.$

So in conclusion we have:

$irr_{t}(J^{*}_{n+1}(x))=irr_{t}(J^{*}_{n}(x))+\sum\limits_{i=1}^{\ell_{1}}i-\sum\limits_{i=1}^{\ell_{2}}i+\sum\limits_{i=1}^{n}|(n-k)-d^{*}(v_{i})|.$
∎

##  3 $f_{t}$-Irregularity of Finite Linear Jaco Graphs

Let
$\mathbb{F}=\\{f_{0}=0,f_{1}=1,f_{2}=1,f_{3}=2,\dots,f_{n}=f_{n-1}+f_{n-2},\dots\\}$
be the set of Fibonacci numbers.

Consider $g:V(G)\mapsto\mathbb{F}$ defined as folows. Allocate the _Fibonacci
weight_ , $f_{i}$ to a vertex $v_{j}$ of a simple connected graph $G,$ if and
only if $d(v_{j})=i.$ Define the _total fibonaccian irregularity_ as,
$firr_{t}(G)=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|f_{i}-f_{j}|.$ For
a simple graph on a singular vertex (_1-empty_ graph), define $firr_{t}(G)=0.$

If all vertices of a graph carry equal fibonacci weight the graph is said to
be $f$-regular. It follows not surprisingly that a regular graph $G$ is _f-
regular_ , hence $firr_{t}(G)=0.$ Note that a connected graph need not be
regular, to be $f$-regular. The path $P_{n},$ $n\in\mathbb{N}$ is the only
example of such non-regular graph which is $f$-regular. Determining
$firr_{t}(G)$ is generally complex but certain graphs provide simple results.
One example is for a star i.e., $firr_{t}(S_{1,n})=n(f_{n}-1).$ Equally
straight forward is that for a complete bipartite graph $K_{n,m},$
$n,m\in\mathbb{N},$ $n\geq m$ we have $firr_{t}(K_{n,m})=nm(f_{n}-f_{m}).$

For illustration the adapted table below follows from the Fisher algorithm
$[3]$ for $J_{n}(x),n\leq 12.$ The $f_{i}$-sequence of $J^{*}_{n}(x)$ is
denoted $\mathbb{F}(J^{*}_{n}(x)).$ Note that for the underlying graphs
$J^{*}_{n}(x),$ the values $firr_{t}(J^{*}_{n}(x))$ have been calculated
manually, as it is not provided for in the Fisher algorithm.

Table 2.
$i\in{\mathbb{N}}$ $d^{-}(v_{i})$ $d^{+}(v_{i})=i-d^{-}(v_{i})$
$\mathbb{F}(J^{*}_{i}(x))$ $firr_{t}(J^{*}_{i}(x))$ 1 0 1 (0) 0 2 1 1 (1, 1) 0
3 1 2 (1, 1, 1) 0 4 1 3 (1, 1, 1, 1) 0 5 2 3 (1, 1, 2, 1, 1) 4 6 2 4 (1, 1, 2,
2, 2, 1) 9 7 3 4 (1, 1, 2, 3, 3, 2, 2) 20 8 3 5 (1, 1, 2, 3, 5, 3, 3, 2) 54 9
3 6 (1, 1, 2, 3, 5, 5, 5, 3, 2) 70 10 4 6 (1, 1, 2, 3, 5, 8, 8, 5, 3, 3) 133
11 4 7 (1, 1, 2, 3, 5, 8, 13, 8, 5, 5, 3) 224 12 4 8 (1, 1, 2, 3, 5, 8, 13,
13, 8, 8, 5, 3) 322

The next result presents a _partially_ recursive formula to determine
$firr_{t}(J^{*}_{n+1}(x))$ if $firr_{t}(J^{*}_{n}(x)),$ $n\geq 1$ is known.

######  Theorem 3.1.

(Lumin’s Theorem)111Named after the young lady, Lumin Bruyns from Klitsgras
who it is hoped will grow up with a deep fondness for mathematics. Consider
the underlying Jaco Graph, $J^{*}_{n}(x),$ $n,x\in\mathbb{N}$ with
$\Delta(J^{*}_{n}(x))=k$ and $firr_{t}(J^{*}_{n}(x))$ known. Let $d(v_{i}),$
$d^{*}(v_{i})$ denote the degree of vertex $v_{i}$ in $J^{*}_{n}(x)$ and
$J^{*}_{n+1}(x)$, respectively. Then for the underlying Jaco graph
$J^{*}_{n+1}(x)$ we have that:

$firr_{t}(J^{*}_{n+1}(x))=firr_{t}(J^{*}_{n}(x))+\sum\limits_{i=1}^{n}|f_{n-k}-f_{d^{*}(v_{i})}|+\sum\limits_{i\in\\{k+1,k+2,\dots,n\\}}\ell_{(1,i)}|f_{d(v_{i})+1}-f_{d(v_{i})}|-\\\
\\\
\sum\limits_{i\in\\{k+1,k+2,\dots,n\\}}\ell_{(2,i)}|f_{d(v_{i})+1}-f_{d(v_{i})}|+\sum\limits_{j=k+1}^{n-1}\sum\limits_{j=i+1}^{n}||f_{d(v_{i})}-f_{d(v_{j})}|-|f_{d(v_{i})+1}-f_{d(v_{j})+1}||,$

with $\ell_{(1,i)}$ the number of vertices $v_{j},j\in\\{1,2,3,\dots,k\\},$
with $d^{*}(v_{i})>d(v_{j}),i\in\\{k+1,k+2,\dots,n\\}$
and $\ell_{(2,i)}$ the number of vertices $v_{j},j\in\\{1,2,3,\dots,k\\},$
with $d^{*}(v_{i})\leq d(v_{j}),i\in\\{k+1,k+2,\dots,n\\}.$

###### Proof.

Let $J^{*}_{n}(x)$ have the prime Jaconian vertex, $v_{k},$ hence
$d(v_{k})=\Delta(J^{*}_{n}(x))$ as defined in $[3].$ It is also true that
$d(v_{k})=\Delta(J^{*}_{n}(x))=d^{*}(v_{k}).$ By adding vertex $v_{n+1}$ to
construct $J_{n+1}(x),$ the vertex $v_{n+1}$ obtains degree,
$d^{*}(v_{n+1})=n-k.$ Each vertex $v_{k+j},j=1,2,\dots,n-k$ obtains an
additional edge, $v_{k+j}v_{n+1}$ as well. So clearly
$d^{*}(v_{k+j})=d(v_{k+j})+1$ for $j=1,2,\dots,n-k.$ We also have that
$d^{*}(v_{i})=d(v_{i}),i=1,2,\dots,k.$ It implies that to calculate
$firr_{t}(J^{*}_{n+1}(1)),$ the term
$\sum\limits_{i=1}^{n}|f_{n-k}-f_{d^{*}(v_{i})}|$ must be added.

For each vertex $v_{i},(k+1)\leq i\leq n$ the _fibonacci weight_ increases by
$|f_{d^{*}(v_{i})}-f_{d(v_{i})}|=|f_{d(v_{i})+1}-f_{d(v_{i})}|.$ It implies
that to calculate $firr_{t}(J^{*}_{n+1}(x)),$ the term
$k(\sum\limits_{i=k+1}^{n}|f_{d(v_{i})+1}-f_{d(v_{i})}|)$ must be added as
well.

Finally, the increase in the $f_{t}$-irregularity between $J^{*}_{n}(x)$ and
$J^{*}_{n+1}(x)$ from amongst vertices, $v_{k+1},v_{k+2},\dots,v_{n}$ is given
by the term,
$\sum\limits_{j=k+1}^{n-1}\sum\limits_{j=i+1}^{n}||f_{d(v_{i})}-f_{d(v_{j})}|-|f_{d^{*}(v_{i})}-f_{d^{*}(v_{j})}||.$

Hence, the result:

$firr_{t}(J^{*}_{n+1}(x))=firr_{t}(J^{*}_{n}(x))+\sum\limits_{i=1}^{n}|f_{n-k}-f_{d^{*}(v_{i})}|+k(\sum\limits_{i=k+1}^{n}|f_{d(v_{i})+1}-f_{d(v_{i})}|)+\sum\limits_{j=k+1}^{n-1}\sum\limits_{j=i+1}^{n}||f_{d(v_{i})}-f_{d(v_{j})}|-|f_{d(v_{i})+1}-f_{d(v_{j})+1}||,$
follows. ∎

###  3.1 $firr_{t}$ Resulting from Edge-joint between Jaco Graphs

Abdo and Dimitrov $[2]$ observed that $irr_{t}(G\cup H)\geq
irr(t(G)+irr_{t}(H)).$ We present a result for $irr_{t}(J^{*}_{n}(x)\cup
J^{*}_{m}(x))$ followed by a corollary in respect of $firr_{t}.$

######  Theorem 3.2.

(Lumin’s 2nd Theorem) For the Jaco Graphs $J^{*}_{n}(x)$ and $J^{*}_{m}(x),$
we have that:

$irr_{t}(J^{*}_{n}(x)\cup J^{*}_{m}(x))\begin{cases}\leq
2(irr_{t}(J^{*}_{n}(x)+irr_{t}(J^{*}_{m}(x)))+\sum\limits_{i=\ell+1}^{n}\sum\limits_{j=n+(\ell+1)}^{m}|d(v_{i})-d(v_{j})|,&\text{if
$n>m,$}\\\ \\\ =4(irr_{t}(J^{*}_{n}(x))),&\text{if $n=m$,}\end{cases}$

with $\ell=\Delta J^{*}_{m}(x).$

###### Proof.

Case 1: Consider the Jaco Graphs $J^{*}_{n}(x)$ and $J^{*}_{m}(x),n>m.$ Label
the vertices $\underbrace{v_{1},v_{2},\dots,v_{n},}_{vertices-
in-J^{*}_{n}(x)}\\\ \underbrace{v_{n+1},v_{n+2},\dots,v_{n+m}}_{vertices-
in-J^{*}_{m}(x)}.$ Let us expand the definition of $irr_{t}(J^{*}_{n}(x)\cup
J^{*}_{m}(x))$ into three parts.

Part(i): In respect of $J^{*}_{n}(x)$ itself, we have the partial sum,

$|d(v_{1})-d(v_{2})|+|d(v_{1})-d(v_{3})|+\dots+|d(v_{1})-d(v_{n-2})|+|d(v_{1})-d(v_{n-1})|+|d(v_{1})-d(v_{n})|+\\\
|d(v_{2})-d(v_{3})|+|d(v_{2})-d(v_{4})|+\dots+|d(v_{2})-d(v_{n-1})|+|d(v_{1})-d(v_{n})|+\\\
|d(v_{3})-d(v_{4})|+|d(v_{3})-d(v_{5})|+\dots+|d(v_{3})-d(v_{n})|+\\\ .\\\
.\\\ .\\\ |d(v_{n-2})-d(v_{n-1})|+|d(v_{n-2})-d(v_{n})|+\\\
|d(v_{n-1})-d(v_{n})|\\\ =irr_{t}(J^{*}_{n}(x)).$

Part (ii): In respect of $J^{*}_{m}(x)$ itself, we have the partial sum,

$|d(v_{n+1})-d(v_{n+2})|+\dots+|d(v_{n+1})-d(v_{(n+m)-2})|+|d(v_{n+1})-d(v_{(n+m)-1})|+|d(v_{n+1})-d(v_{n+m})|+\\\
|d(v_{n+2})-d(v_{n+3})|+\dots+|d(v_{n+2})-d(v_{(n+m)-1})|+|d(v_{n+2})-d(v_{n+m})|+\\\
|d(v_{n+3})-d(v_{n+4})|+\dots+|d(v_{n+3})-d(v_{n+m})|+\\\ .\\\ .\\\ .\\\
|d(v_{(n+m)-2})-d(v_{(n+m)-1})|+|d(v_{(n+m)-2})-d(v_{n+m})|+\\\
|d(v_{(n+m)-1})-d(v_{n+m})|\\\ =irr_{t}(J^{*}_{m}(x)).$

Part (iii): In respect of $J^{*}_{n}(x)$ towards $J^{*}_{m}(x)$ we have the
partial sum,

$|d(v_{1})-d(v_{n+1})|+|d(v_{1})-d(v_{n+2})|+\dots+|d(v_{1})-d(v_{n+m})|+\\\
|d(v_{2})-d(v_{n+1})|+|d(v_{2})-d(v_{n+2})|+\dots+|d(v_{2})-d(v_{n+m})|+\\\
.\\\ .\\\ .\\\
|d(v_{n})-d(v_{n+1})|+|d(v_{n})-d(v_{n+2})|+\dots+|d(v_{n})-d(v_{n+m})|=\\\
\\\ 0+|d(v_{1})-d(v_{n+2})|+\dots+|d(v_{1})-d(v_{n+m})|+\\\
|d(v_{2})-d(v_{n+1})|+0+|d(v_{2})-d(v_{n+3})|+\dots+|d(v_{2})-d(v_{n+m})|+\\\
|d(v_{3})-d(v_{n+1})|+|d(v_{3})-d(v_{n+2})|+0+|d(v_{3})-d(v_{n+4})|+\dots+|d(v_{3})-d(v_{n+m})|+\\\
.\\\ .\\\ .\\\
\underbrace{|d(v_{\ell})-d(v_{n+1})|+\dots+\underbrace{0}_{\ell^{th}-term}+|d(v_{\ell})-d(v_{n+(\ell+1)})|+\dots+|d(v_{\ell})-d(v_{n+m})|}_{\ell^{th}-row}+\\\
\\\
|d(v_{\ell+1})-d(v_{n+1})|+|d(v_{\ell+1})-d(v_{n+2})|+\dots+|d(v_{\ell+1})-d(v_{n+m})|+\\\
.\\\ .\\\ .\\\
|d(v_{n})-d(v_{n+1})|+|d(v_{n})-d(v_{n+2})|+\dots+|d(v_{n})-d(v_{n+m})|.$

By observing that a term $|d(v_{i})-d(v_{j})|,1\leq i\leq\ell$ and $i\leq
j\leq(n+i)-1$ can be converted to $|d(v_{i})-d(v_{j})|=|d(v_{j-n})-d(v_{i})|,$
with $|d(v_{n-j})-d(v_{i})|$ a term of
$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|_{v_{i},v_{j}\in
J^{*}_{n}(x)}.$ It is also noted that a term $|d(v_{i})-d(v_{j})|,\ell+1\leq
i\leq n$ and $n+1\leq j\leq n+\ell$ can be converted to
$|d(v_{i})-d(v_{j})|=|d(v_{j-n})-d(v_{i})|,$ with $|d(v_{n-j})-d(v_{i})|$ a
term of
$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|_{v_{i},v_{j}\in
J^{*}_{n}(x)}.$

Similarly, by observing that a term $|d(v_{i})-d(v_{j})|,1\leq i\leq\ell-1$
and $n+2\leq j\leq n+\ell$ can be converted to
$|d(v_{i})-d(v_{j})|=|d(v_{n+i})-d(v_{j})|,$ with $|d(v_{n+i})-d(v_{j})|$ a
term of
$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|_{v_{i},v_{j}\in
J^{*}_{m}(x)}.$ It is also noted that a term $|d(v_{i})-d(v_{j})|,1\leq
i\leq\ell$ and $(n+\ell)+1\leq j\leq n+m$ can be converted to
$|d(v_{i})-d(v_{j})|=|d(v_{j-n})-d(v_{i})|,$ with $|d(v_{n+i})-d(v_{j})|$ a
term of
$\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|d(v_{i})-d(v_{j})|_{v_{i},v_{j}\in
J^{*}_{m}(x)}.$

Finally it is observed that the terms $|d(v_{i})-d(v_{j})|\geq 0,\ell+1\leq
i\leq n+m$ and $(n+\ell)+1\leq j\leq n+m$ cannot be converted.

Hence, the result:

$irr_{t}(J^{*}_{n}(x)\cup J^{*}_{m}(x))\leq
2(irr_{t}(J^{*}_{n}(x))+irr_{t}(J^{*}_{m}(x)))+\sum\limits_{i=\ell+1}^{n}\sum\limits_{j=n+(\ell+1)}^{m}|d(v_{i})-d(v_{j})|,$
follows.

Case 2: Parts (i) and (ii) follow similarly to that of Case 1.

Part (iii): In respect of $J^{*}_{n}(x)$ towards $J^{*}_{n}(x)$ we have the
partial sum,

$|d(v_{1})-d(v_{n+1})|+|d(v_{1})-d(v_{n+2})|+\dots+|d(v_{1})-d(v_{2n})|+\\\
|d(v_{2})-d(v_{n+1})|+|d(v_{2})-d(v_{n+2})|+\dots+|d(v_{2})-d(v_{2n})|+\\\
.\\\ .\\\ .\\\
|d(v_{n})-d(v_{n+1})|+|d(v_{n})-d(v_{n+2})|+\dots+|d(v_{n})-d(v_{2n})|=\\\ \\\
0+|d(v_{1})-d(v_{n+2})|+\dots+|d(v_{1})-d(v_{2n})|+\\\
|d(v_{2})-d(v_{n+1})|+0+|d(v_{2})-d(v_{n+3})|+\dots+|d(v_{2})-d(v_{2n})|+\\\
|d(v_{3})-d(v_{n+1})|+|d(v_{3})-d(v_{n+2})|+0+|d(v_{3})-d(v_{n+4})|+\dots+|d(v_{3})-d(v_{2n})|+\\\
.\\\ .\\\ .\\\
|d(v_{n})-d(v_{n+1})|+|d(v_{n})-d(v_{n+2})|+\dots+|d(v_{n})-d(v_{2n-1})|+\underbrace{0}_{n^{th}-term}.$

So similary to the _term conversion rules_ of Part (iii) above in Case 1 we
calculate exactly another $irr_{t}(J^{*}_{n}(x))$ on the _left under of
0-entries_ and another $irr_{t}(J^{*}_{n}(x))$ on the _right upper of
0-entries_. So, Parts (i), (ii) and (iii) added together gives the result:

$irr_{t}(J^{*}_{n}(x)\cup J^{*}_{n}(x))=4(irr_{t}(J^{*}_{n}(x))).$ ∎

######  Corollary 3.3.

For the Jaco Graphs $J^{*}_{n}(x)$ and $J^{*}_{m}(x),$ we have that:

$firr_{t}(J^{*}_{n}(x)\cup J^{*}_{m}(x))\begin{cases}\leq
2(firr_{t}(J^{*}_{n}(x)+firr_{t}(J^{*}_{m}(x)))+\sum\limits_{i=\ell+1}^{n}\sum\limits_{j=n+(\ell+1)}^{m}|f_{d(v_{i})}-f_{d(v_{j})}|,&\text{if
$n>m$,}\\\ \\\ =4(firr_{t}(J^{*}_{n}(x))),&\text{if $n=m$.}\end{cases}$

###### Proof.

Similar to the proof of Theorem 2.2. ∎

######  Definition 3.1.

The edge-joint of two simple undirected graphs $G$ and $H$ is the graph
obtained by linking the edge $vu,$ $v\in V(G),u\in V(H)$ and denoted,
$G\rightsquigarrow_{vu}H.$

######  Lemma 3.4.

Consider the underlying Jaco graphs $J^{*}_{n}(x)$ and $J^{*}_{m}(x)$ on the
vertice $v_{1},v_{2},v_{3},\dots,v_{n}$ and $u_{1},u_{2},u_{3},\dots,u_{m}$,
respectively, then $firr_{t}(J^{*}_{n}(x)\cup
J^{*}_{m}(x))=firr_{t}(J^{*}_{n}(x)\rightsquigarrow_{v_{1}u_{1}}J^{*}_{m}(x)).$

###### Proof.

Since $d(v_{1})=1$ and $d(u_{1})=1$ in $J^{*}_{n}(x)$ and $J^{*}_{m}(x)$
respectively, the _fibonacci weight_ of $v_{1},$ $u_{1}$ equals $f_{1}=1,$
respectively. In the graph
$J^{*}_{n}(x)\rightsquigarrow_{v_{1}u_{1}}J^{*}_{m}(x)$, we have that
$d(v_{1})=2,d(u_{1})=2$ with both fibonacci weights remaining 1, so the result
follows. ∎

######  Theorem 3.5.

Consider the underlying graphs $J^{*}_{n}(x),$ $n\geq 3$ and $J^{*}_{m}(x),$
$m\geq 1$ on the vertices $v_{1},v_{2},v_{3},\dots,v_{n}$ and
$u_{1},u_{2},u_{3},\dots,u_{m}$, respectively. Without loss of generality
choose any vertex $v_{i},i\neq 1$ from $V(J^{*}_{n}(x)).$ Let
$V_{1}=\\{v_{x}|f_{d(v_{x})}\leq f_{d(v_{i})}\\},|V_{1}|=a;$
$V_{2}=\\{v_{y}|f_{d(v_{y})}>f_{d(v_{i})}\\},|V_{2}|=b;$
$V_{3}=\\{u_{x}|f_{d(u_{x})}\leq f_{d(v_{i})}\\},|V_{3}|=a^{*}$ and
$V_{4}=\\{u_{y}|f_{d(u_{y})}>f_{d(v_{i})}\\},|V_{4}|=b^{*}.$ For the simple
connected graph
$G^{\prime}=J^{*}_{n}(x)\rightsquigarrow_{v_{i}u_{1}}J^{*}_{m}(x)$ we have
that:

$firr_{t}(G^{\prime})=firr_{t}(J^{*}_{n}(x))+firr_{t}(J^{*}_{m}(x))+\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{m}|f_{d(v_{j})}-f_{d(u_{k})}|_{v_{j}\in
V(J^{*}_{n}(x)),u_{k}\in
V(J^{*}_{m}(x))}+\sum\limits_{j=1}^{a}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in
V_{1}}-\sum\limits_{j=1}^{b}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in
V_{2}}+\sum\limits_{j=1}^{a^{*}}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in
V_{3}}-\sum\limits_{j=1}^{b^{*}}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in V_{4}}.$

###### Proof.

Clearly for $G=J^{*}_{n}(x)\cup J^{*}_{m}(x)$ we have that
$firr_{t}(G)=firr_{t}(J^{*}_{n}(x))+firr_{t}(J^{*}_{m}(x))+\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{m}|f_{d(v_{j})}-f_{d(u_{k})}|_{v_{j}\in
V(J^{*}_{n}(x)),u_{k}\in V(J^{*}_{m}(x))}.$

Since $f_{1}=f_{2}=1$, increasing $d(u_{1})$ by 1 has no effect on the value
of $firr_{t}(J^{*}_{n}(x)\rightsquigarrow_{v_{i}u_{1}}J^{*}_{m}(x)).$ By
increasing $d(v_{i})$ by 1 we increase the value of
$firr_{t}(J^{*}_{n}(x)\rightsquigarrow_{v_{i}u_{1}}J^{*}_{m}(x))$ by exactly
$|f_{d(v_{i})}-f_{d(v_{j})}|_{1\leq j\leq a}$ in respect of $J^{*}_{n}(x).$ So
the total partial increase is given by sum
$(\sum\limits_{j=1}^{a}|f_{d(v_{i})}-f_{d(v_{j})}|)_{v_{j}\in V_{1}}.$ It also
reduces the value of
$firr_{t}(J^{*}_{n}(x)\rightsquigarrow_{v_{i}u_{1}}J^{*}_{m}(x))$ by exactly
$|f_{d(v_{i})}-f_{d(v_{j})}|_{1\leq j\leq b}.$ So the total partial decrease
is given by $(\sum\limits_{j=1}^{b}|f_{d(v_{i})}-f_{d(v_{j})}|)_{v_{j}\in
V_{2}}.$

In respect of $J^{*}_{m}(x)$ it also increases the the value of
$firr_{t}(J^{*}_{n}(x)\rightsquigarrow_{v_{i}u_{1}}J^{*}_{m}(x))$ by exactly
$|f_{d(v_{i})}-f_{d(v_{j})}|_{1\leq j\leq a^{*}}.$ So the total partial
increase is given by
$(\sum\limits_{j=1}^{a^{*}}|f_{d(v_{i})-d(v_{j})}|)_{v_{j}\in V_{3}}.$ It also
reduces the value of
$firr_{t}(J^{*}_{n}(x)\rightsquigarrow_{v_{i}u_{1}}J^{*}_{m}(x))$ by exactly
$|f_{d(v_{i})}-f_{d(v_{j})}|_{1\leq j\leq b^{*}}.$ So the total partial
decrease is given by
$(\sum\limits_{j=1}^{b^{*}}|f_{d(v_{i})}-f_{d(v_{j})}|)_{v_{j}\in V_{4}}.$

Hence, the result:

$firr_{t}(G^{\prime})=firr_{t}(J^{*}_{n}(x))+firr_{t}(J^{*}_{m}(x))+\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{m}|f_{d(v_{j})}-f_{d(u_{k})}|_{v_{j}\in
V(J^{*}_{n}(x)),u_{k}\in
V(J^{*}_{m}(x))}+\sum\limits_{j=1}^{a}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in
V_{1}}-\sum\limits_{j=1}^{b}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in
V_{2}}+\sum\limits_{j=1}^{a^{*}}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in
V_{3}}-\sum\limits_{j=1}^{b^{*}}|f_{d(v_{i})}-f_{d(v_{j})}|_{v_{j}\in V_{4}},$
follows. ∎

##  4 Conclusion

The allocation of Fibonacci weights to the vertices of graphs as a function of
vertex-degree is a variation of graph labeling. Deriving a useful edge
labeling from the primary vertex labeling is still open. From this study the
following can be pursued:

(i) Describe a well-defined algorithm that determines the result of Theorem
1.1,
(ii) Describe a well-defined algorithm that determines the result of Theorem
2.1.

$f$-Irregularity can be studied for a number of classes of graphs such as
paths, cycles, trees and for graph operations. Furthermore, we propose the
following vertex labeling study. Define the $\pm$_Fibonacci weight_ ,
$f_{i}^{\pm}$ of a vertex $v_{j}$ to be $-f_{d(v_{j})},$ if $d(v_{j})$ is odd
and, $f_{d(v_{j})},$ if $d(v_{j})$ is even. Determine
$firr_{t}^{\pm}(G)=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}|f_{i}^{\pm}-f_{j}^{\pm}|$
in general or for some special classes of graphs. For example,
$firr_{t}^{\pm}(P_{n})=4(n-2)$ and
$firr_{t}^{\pm}(C_{n})=firr_{t}(C_{n})=irr_{t}(C_{n})=0.$ The latter result
holds for all regular graphs.

Because total irregularity presents a sum of differences between all pairs of
natural numbers in a subset $X\subset\mathbb{N}$ for $X$ having an even number
of odd numbers we see that $f_{t}$-irregularity is the specialisation thereof
by mapping on Fibonnaci numbers. This allows for studies where mapping on
complex numbers or other number classes or families of _number abstractions_
which have the notions of _even abstractions_ and _odd abstractions_ imbedded,
to be considered. Clearly such number abstraction could be a graph. For
example let a path on $n$ vertices be $v_{1}e_{1}v_{2}e_{2}v_{3}e_{3}\dots
e_{n-1}v_{n}.$ For a vertex $v\in V(G)$, $d_{G}(v)=k$ add the path $P_{k}$ as
an _ear_ to vertex $v$ by adding the edges $vv_{1}$, $vv_{n}$. An _path-eared_
graph is denoted, $G^{\mathcal{P}}$. Assume the chromatic number of paths is
the invariant. Define total $\chi$-irregularity or $\chi_{t}$-irregularity as
$\chi_{t}(G^{\mathcal{P}})=\frac{1}{2}\sum\limits_{u,v\in
V(G)}|\chi(P_{d(u)})-\chi(P_{d(v)})|.$ Furthering a study for certain classes
of graphs $\mathcal{H}$ with $H\in\mathcal{H},$ $|V(H)|\geq 2$ to be _H-eared_
to the vertices of $G$ and selecting any invariant $\mu$ to define
$\mu_{t}$-irregularity is worthy. Furthemore, if a meaningful definition for
edge labeling can be found for a $H$-eared graph, a new field of total graph
labeling may be researched.

_Open access:_ This paper is distributed under the terms of the Creative
Commons Attribution License which permits any use, distribution and
reproduction in any medium, provided the original author(s) and the source are
credited.

References (Limited)

$[1]$ H. Abdo, S. Brandt, H. Dimitrov, _The total irregularity of a graph,_
Discrete Mathematics and Theoretical Computer Science, Vol 16(1), (2014),
201-206.
$[2]$ H. Abdo, D. Dimitrov, _The total irregularity of a graph under graph
operations,_ Miskolc Mathematical Notes, Vol 15 (1) (2014) 3-17.
$[3]$ J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan
Press, London, (1976).
$[4]$ 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.
$[5]$ 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.
$[6]$ J. Kok, C. Susanth, S.J. Kalayathankal, _A Study on Linear Jaco Graphs_
, Journal of Informatics and Mathematical Sciences, Vol 7(2), (2015), 69-80.
$[7]$ Y. Zhu, L. You, J. Yang, _The Minimal Total Irregularity of Graphs,_
arXiv: 1404.0931v1 [math.CO], 3 April 2014.


Automated Driving Systems (ADS) development  relies on utilizing  real-world vehicle data. The volume of data generated by modern vehicles presents  transmission, storage, and computational challenges.  Focusing on dvb offers a promising approach to distinguish relevant from irrelevant information for ADS functionalities, thereby reducing data. Time series pattern recognition is beneficial for this task as it can analyze the temporal context of vehicle driving behavior. However, existing state-of-the-art methods often lack the adaptability to identify variable-length patterns or provide analytical descriptions of discovered patterns.
This contribution proposes a Behavior Forest framework for real-time data selection by constructing a Behavior Graph during vehicle operation, facilitating analytical descriptions without pre-training.
The method demonstrates its performance using a synthetically generated and electrocardiogram data set. An automotive time series data set is used to evaluate the data reduction capabilities, in which this method discarded $\SI{96.01}{\percent}$ of the incoming data stream, while relevant dvb remain included.

§ INTRODUCTION

Real-world vehicle data is used in all development phases of  Automated Driving Systems (ADS)  <cit.> including risk analysis <cit.>, perception, path planning and control <cit.> or simulation and critical scenario identification <cit.>.
These possibilities for utilizing vehicle data face the challenge of dealing with the influx of data during vehicle operation.
Modern vehicles equipped with cameras, RADAR, and LiDAR can generate up to $\SI{40}{\giga\byte\per\second}$ of data <cit.>. With an average driving time of one hour per day and approximately 60 million vehicles in Germany, this would result in a data volume of $8,64$ zetta bytes ($\SI{8.64e12}{\giga\byte}$) of data per year, which is an order of magnitude more data than the current capacity of the data center of the European Organisation for Nuclear Research (CERN) can hold <cit.>. Furthermore, recording these data would be associated with enormous transmission, storage, and computation costs, making it economically and technically inefficient or impossible <cit.>. As a result, recording all these data volumes is impractical, necessitating a selective approach to recording. This begs the question: How can the influx of data be efficiently managed, and how can data recording during vehicle operation be triggered to obtain a relevant data set for ADS development?In ADS, developers are interested in Dynamic Behavior (DB) data described by time series like velocity or steering signals. Additionally, considering that *dvb happens at different frequencies, such as lane changes on highways being more common than evasive behavior, evaluating relevance regarding information redundancy is essential. The potential of real-time data selection techniques is demonstrated in physics research at the CERN institute <cit.>. In an experiment conducted with the Large Hadron Collider, $\SI{40}{\tera\byte\per\second}$ of data are generated. However, using run-time selection techniques,  $\SI{99,98}{\percent}$ of data can be removed <cit.>.
In the automotive domain, Tesla uses a shadow-mode, which records data if a mismatch between a driver and the vehicle trajectory prediction occurs <cit.>, which is rather an error detector than a holistic approach for data recording.

Concept for recording or discarding vehicle data during operation using a  Behavior Forest approach.

Time Series Analysis provides a variety of methods  to examine sequential data effectively. For instance, it enables the discovery of recurring patterns in time-series data, known as PR <cit.>, which in this context refers to *dvb.
Current approaches to PR methods cannot learn what is already known during operation, identify patterns of variable length, or describe the identified patterns analytically.
This contribution addresses these challenges by proposing a Behavior Forest  for *dvb discovery of variable length explicitly designed for real-time data selection, see Fig. <ref>. This entails identifying unseen *dvb, learning their representation, and recording them if they are assessed as relevant while disregarding non-dynamic and already known irrelevant dynamic behavior.

§.§ Related Works

Methods for PR  encompass various approaches, including sliding window techniques, signal thresholding, transformer models, and tree graphs. Especially, methods reliant on signal thresholds for detecting the initiation and termination of *dvb are straightforward to implement, such as thresholds applied to lateral and longitudinal acceleration <cit.> or rotational energy <cit.>. However, these methods often lack detailed characterization of *dvb progression and may oversimplify data recording conditions.
A widely adopted strategy for PR involves employing a sliding window across the time series. This method  utilizes raw signal values or derived features from rolling time windows, which are subsequently employed in (un)supervised learning models for classification tasks <cit.>. Despite its efficacy, the sliding window approach necessitates careful consideration of two critical hyperparameters: the window size, which dictates the temporal span of a *dvb, and the window overlap. Suboptimal settings for these parameters, such as zero window overlap leading to information loss or maximal window overlap yielding meaningless results, have been discussed in <cit.>.
Recently, transformer architectures with self-attention mechanisms have emerged as promising tools for time series analysis, finding applications in various domains <cit.>. However, despite their success in natural language processing tasks, concerns have been raised regarding their applicability in time series analysis due to inherent features like positional encoding and tokenization <cit.>.
Additionally, formalizing discovered patterns interpretatively to extract actionable knowledge and facilitate continual learning processes is challenging, often complicated by issues such as the catastrophic forgetting phenomenon <cit.>.
In  time series analysis, tree graphs have been utilized for tasks such as forecasting <cit.> and anomaly detection <cit.> through methods like isolation trees. While effective, these approaches typically require training data and are not commonly explicitly employed for pattern identification.
Moreover, none of the aforementioned approaches can learn from identified patterns and organize them meaningfully  to address the challenge of selecting data by a specific data distribution condition of discovered patterns.

§.§ Contribution and Outline

The contribution of this paper unfolds in two main aspects:
Firstly, it introduces an approach for PR of variable length without pre-training. These patterns are systematically structured analytically  through a bottom-up construction of a Behavior Forest, effectively compressing observed data. This approach represents a continual learning process.
Secondly, it proposes an approach for real-time data selection  by solely recording relevant *dvb.
This method is analyzed for PR using a synthetic and an electrocardiogram (ECG) data set.
Additionally, experimental results from an automotive time series data set showcase its efficacy in handling data and facilitating real-time data recording trigger actions based on discovered *dvb.

Section <ref> presents the necessary notation and definitions essential for PR in this paper, while Section <ref> introduces the conceptual framework for discovering relevant *dvb, outlining all its components. Section <ref> thoroughly evaluates and discusses the method. Finally, Section <ref> summarizes the findings of this contribution and provides insights into potential future research avenues.

§ PRELEMINARIES

Before delving into the concepts of the proposed method, the following terms are defined:

A d-dimensional time series w.r.t. a series of time points ${\mathbb{T}}=\{t_{1},...,t_{n}\}$ of length $n\in\mathbb{N}$ is $\mathcal{T}=\{(t_{i},y_{i}){\vert y_{i}}= (y_{i,1},...,y_{i,d})^{T}\in\mathbb{R}^{d}, t_{i}\in\mathbb{T}, i=1,\cdots,n\}$. If $d=1$, $\mathcal{T}$ is called univariate, for $d > 1$ it is a multivariate time series.

A subsequence $\mathcal{T}_{i,l} \in \mathbb{R}^{n\times d+1}$ of a time series $\mathcal{T}$ is a subset of values from $\mathcal{T}$ of length $l$ starting from index $i$. This subsequence $\mathcal{T}_{i,l}$ contains consecutive tuples $\begin{bmatrix}t_{i} &t_{i+1}&\hdots&t_{i+l-1}\end{bmatrix}$.

A time series pattern $\mathcal{P}$ is a group of m (with $m \geq 2$) similar subsequences in a time series $\mathcal{T}$. A subsequence $\mathcal{T}_{i,\mathrm{l}}$ , that is
included in a pattern $\mathcal{P}$, is called a member M. Formally, $\mathcal{P} = [M_1, M_2, \hdots , M_m]$ with each $M_x$ being a subsequence with a starting index i and a length l. This includes a distance threshold $\tau$ with $ dist(M_x , M_y) \leq \tau, \, \forall x, y \in [1, \hdots,m]$.

A Dynamic Behavior (DB) is a pattern $\mathcal{P}$ that initiates from and concludes in a stationary  state.

The goal of the real-time dvb discovery is to find the dvb during operation and trigger the recording if a  relevance criteria is met.

§ CONCEPT

The proposed method for discovering dvb in a continuous data stream comprises two steps: A preprocessing step based on <cit.>, which is designed for discovering vehicle driving patterns involving discretization, hysteresis filtering, dimension, and numerosity reduction – Moreover, the construction of a Behavior Forest, which is the main contribution of this paper.

Preprocessing of data. The raw multivariate time signals (left, ) are discretized with predefined breakpoints (middle left, ). Using unification, the multivariate time series is transformed into a univariate time series (middle right, ) and finally compressed with a logarithmic numerosity reduction method (right, ).

§.§ Preprocessing

§.§.§ Discretization

Symbolic Aggregate Approximation (SAX) is a method utilized to transform the original signal into a symbolic representation using predefined thresholds, thereby reducing computational resources as demonstrated in <cit.>, see Fig. <ref> (a) to (b).

Given a natural number $\alpha\geq2$, define $\probP \coloneqq \begin{pmatrix}\frac{1}{\alpha} \vert 1,\hdots ,\alpha \end{pmatrix}$. Applying the quantile function of the standard normal distribution to the probabilities in $\probP$
results in the $\alpha$-quantiles $\beta_j$ with $1\leq j\leq \alpha$ of the standard normal distribution.
The ascending sorted list of these $\alpha$-quantiles

\begin{equation}\label{eq:breakpoints}
\mathrm{B} \coloneqq \begin{bmatrix}\beta_0, \beta_1, \hdots ,\beta_{\alpha}  \end{bmatrix}
\end{equation}

with $\beta_0 = -\infty$ and $\beta_\alpha = +\infty$ are called breakpoints and $\alpha$ is called alphabet size.

This way, a time series $\mathcal{T}$ is transformed in a symbolic time series $\mathcal{T}_{\mathrm{s}}$, using the discretization function $f_\mathrm{s}$

\begin{equation}
f_\mathrm{s}:\mathcal{T}\rightarrow \mathcal{T}_{\mathrm{s}}.
\end{equation}

§.§.§ Hysteresis Filter

Signals which are in the value regions of the breakpoints $\beta_i$ from (<ref>) are prone to lead to symbolic toggling due to noise. This is eliminated by the hysteresis filter <cit.>.

§.§.§ Dimension Reduction

Reducing the dimensionality of multivariate time series increases the computation efficiency of PR, which can be rule-based, spectral, probabilistic, and unsupervised learning-based <cit.>. Except for rule-based dimension reduction methods, these approaches need data in advance for parameter tuning. Therefore, this paper uses the rule-based method unification by mapping all combinations of discretization symbols to a unique symbol using the cartesian product, see Fig. <ref> (b) to (c). For two discretized signals $B_{\mathrm{1}}$ and $B_{\mathrm{2}}$, this leads to unified discretization breakpoints $B_{\mathrm{u}}$:

\begin{equation}\label{eq:dimReduciton}
B_{\mathrm{u}} = B_{\mathrm{1}} \times B_{\mathrm{2}}.
\end{equation}

§.§.§ Numerosity Reduction

Numerosity Reduction is a data reduction technique that aims to reduce the number of data points while preserving its essential characteristics, see Fig. <ref> (c) to (d). The consideration of temporally distorted signals as the same pattern is approached with a logarithmic reduction of the symbol sequence with the base $a$, that is, for each subsequence of the same symbol $\mathcal{S}_{\mathrm{same}}$ leading to a numerosity reduced subsequence $\mathcal{S}_{\mathrm{reduced}}$:

\begin{equation}
L\left(\mathcal{S}_{\mathrm{reduced}} \right) = \lceil \log_a{L(\mathcal{S}_\mathrm{same}} )\rceil
\end{equation}

where $L(\mathcal{S}_\mathrm{same})$ is the length of consecutive identical symbols in a subsequence  and  $\lceil X \rceil$ being the ceiling function.

These preprocessing steps reduce the computational complexity of the time series while preserving the pattern characteristics. Based on this preprocessing, the discovery and analytical description take place using the Behavior Forest.

§.§ Continual dvb Discovery with Behavior Forests

Time sequence

Behavior Tree

Exemplary construction of a Behaviour Tree  from a time sequence with the indicated dvb.

The core of pattern identification lies in the bottom-up construction of a Behavior Tree, illustrated in Fig. <ref>. The tree structure (right) adapts as the algorithm processes the data stream (left), ultimately contributing to the broader Behavior Forest.
The algorithm identifies the initiation of a dvb when a symbol differs from the two preceding symbols of the same value.
Upon detecting a dvb initiation, the construction of a Behavior Tree commences. Subsequently, the first symbol in the dvb sequence becomes the root node of this tree.
As subsequent symbols arrive from the data stream, the algorithm traverses the Behavior Tree, searching for a child node of the current node that matches the incoming symbol. If a matching child node exists, the traversal continues down that branch,  indicating that the observed sequence aligns with a previously encountered dvb. However, if no matching child node exists, a new child node is created for the incoming symbol, signifying the discovery of a new element within the dvb pattern, as indicated in green. The traversal then proceeds down the newly created branch, extending the tree structure.
The traversal continues until a termination condition is met. This can occur when the data stream indicates a steady-state driving scenario identified by three consecutive symbols. Leaf nodes in the Behavior Tree represent the final symbols of a dvb.  Besides analytically describing dvb, the algorithm tracks the frequency of each dvb, indicated by the edge weight of the Behaviour Tree. With each identified dvb and its corresponding Behavior Tree construction, the frequency count associated with the leaf node increments. This functionality allows the algorithm to identify dvb and quantify their prevalence within the data stream.
Overall, the Behavior Tree construction process enables the algorithm to dynamically capture the structure and occurrence frequency of dvb observed in the continuous data stream.

Visualization of the two-dimensional synthetic time series in (a, top), in which signal one is orange  and signal two is blue . An extract of the Behavior Forest (b) represents four distinct patterns as a colored leafs. These colored leafs are highlighted according to the pattern in the original time series (a, top), and in the preprocessed symbolic sequence (a, bottom) which is the Behavior Forest algorithm input.

§ NUMERICAL EVALUATION

The evaluation is divided into two sections: the first section assesses the discovery of patterns in two different data sets, while the second part evaluates the application of data reduction in a vehicle speed data set by discovering dvb for data selection.

§.§ Discovery of Patterns

§.§.§ Synthetic Time Series

For a demonstration of PR according to Definition <ref>, a two-dimensional time series with four patterns consisting of alternating sawtooth and sinus wave signals with amplitudes of $a_1=1$ and $a_2=0.6$  with added Gaussian noise are generated, see Fig. <ref> (top). The pattern discovery algorithm uses the parameter according to table <ref>.

Parameter Values Synthetic Data

Parameter     Value

logarithmic base $a$      10

$B_{\mathrm{1}/\mathrm{2}}$     $\left[ -0.5, 0.5 \right]$

The resulting Behavior Forest contains four leafs indicating four different patterns, as shown in Fig.  <ref>. The colored patterns  are shown in the original time series and in the preprocessed symbolic sequence. All multivariate patterns are found in the preprocessed data and  represented in the Behavior Graph.

§.§.§ Electrocardiogram Recording

A popular time series for analysis is the open-source electrocardiogram  (ECG) recording <cit.> since the patterns are labeled as normal and abnormal. For evaluation, the behavior Forest method is applied to the normal, see Fig. <ref>  in blue , and abnormal, see Fig. <ref> in orange , ECG recording separately. The parameters are set according to table <ref>.

Parameter Values ECG Data

Parameter     Value

logarithmic base $a$      10

$B$     $\left[ 0,0.2,0.4,0.6,0.8,1 \right]$

The Behavior Forest extracted 80 patterns from normal and 6 patterns from abnormal ECG data set. From each pattern, nine features are extracted which are: mean, variance, skew, kurtosis min, max, median, 25 and 75 percentil. This nine-dimensional feature vector of each pattern is visualized using the t-SNE algorithm into a two-dimensional plane, see Fig. <ref>. A blue dot  indicates a normal ECG signal whereas an orange dot  indicates an abnormal ECG signal. It can be seen that some pattern features occur in both signals. However, compared to the normal ECG data set, the abnormal data set has a disturbed ECG signal between $t_\mathrm{start}=0s$ and $t_\mathrm{end}\approx 0.5s$. These resulting patterns lead to the blue dominating pattern features. Consequently, the behavior Forest method discovered patterns that are both present in the normal and abnormal, and patterns that are only present in one of the normal or abnormal ECG data sets, allowing them to be distinguished.

Subset of normal / and abnormal / ECG time signals (left). Visualizing the features of found patterns (mean, variance, skew, kurtosis, minimum, maximum, median, 25th, and 75th percentiles) in a two-dimensional plane using the t-SNE algorithm (right).

§.§ Vehicle Data Selection

To demonstrate the method for real-time data selection, the vehicle speed data set containing 5973 rides with a total length of $9049.3$km  <cit.> is used for evaluation. The vehicle speed is generated synthetically using LSTMs with a speed range of $v_{\min}=0$ km/h and $v_{\max}= 130$ km/h. For the discovery of dvb with the proposed method, the parameters are set according to table <ref>.

Parameter Values Vehicle Data

Parameter     Value

logarithmic base $a$      10

$B$     $\left[ 0, 5, 10, 17.5,25, 35, 45, 55, 70 \right]$

For evaluation of the data selection, the entire data set is repeated several times to simulate a progression from no prior knowledge to a known driving situation. The evaluation starts with an empty Behavior Forest, representing zero prior knowledge of the course.  The criteria for data recording are:

* A leaf is created in the Behavior Forest, which indicates an unseen dvb.

* A known dvb is considered relevant if it has occurred less than five times.

During the initial run, 697 dvb were detected, comprising $\SI{8.89}{\percent}$ of the complete data set. However, by the fifth run, all data was discarded, as indicated in Table <ref>. Consequently, the amount of recorded data decreases progressively, which indicates a learning process of the discovered dvb inside the data set.

Recording of Vehicle Data

Run 1    Run 2    Run 3    Run 4    Run 5

Recorded dvb       697      383    277    171     0

Recording/Run     $\SI{8.89}{\percent} $    $\SI{5.02}{\percent} $    $\SI{3.78}{\percent} $    $\SI{2.3}{\percent} $     $\SI{0}{\percent}$

Total Recording     $\SI{8.89}{\percent} $    $\SI{6.96}{\percent} $    $\SI{5.90}{\percent} $    $\SI{4.99}{\percent} $     $\SI{3.99}{\percent}$

Overall, $\SI{3.99}{\percent}$ of the data are recorded with 1528 dvb detections. By discarding $\SI{96.01}{\percent}$ of the data stream, the recorded data needs evaluation to determine if they represent the desired dvb data. Therefore, the variance of the recorded data is computed and compared against the variance of a sliding window across the data set with $\SI{50}{\percent}$ overlap. The window length is set to the mean of all discovered dvb, as depicted in Fig. <ref>. It is evident that the selected recorded data represent time series with high variance, indicating a more dynamic movement.

Comparison of the signal variance of the recorded dvb data and sliding window across the whole data set.

Six different driving speed signals from the data set, with the variable-length dvb highlighted in green, recorded using the Behavior Forest method. Darker green highlights indicates a detected sub-pattern within a pattern.

Additionally, six of the 5973 rides are shown in Fig. <ref> with the recorded data, in which the detected dvb are marked in green. It can be seen that both dynamic and variable length dvb were recorded, which underlines the performance of the proposed method.

§.§ Discussion and Limitations

Besides the effectiveness of the proposed method, two other aspects need to be discussed.
First, the criteria for relevant data is set to a threshold of five occurrences in the application of data selection. For real-world applications, more advanced criteria should be considered.
Second, the proposed method utilizes two hyperparameters: discretization breakpoints and logarithmic reduction basis, which must be set.  Expert knowledge is necessary to set these hyperparameters properly. However, in applications like dvb detection, where ranges of the dynamical system are known, determining suitable breakpoints $\beta_i$ and temporal scaling becomes feasible. Therefore, the limitation of this method lies only in applications where no prior information about the data is available.

§ CONCLUSION & OUTLOOK

Compared to state-of-the-art methods for discovering Dynamic Behavior (DB) in  time series data, the proposed approach excels in several aspects. It identifies dynamic behavior of variable length without pre-training, operating in a continual learning manner. Real-time data preprocessing and bottom-up construction of a Behavior Forest provides an analytical representation of dvb, enabling effective data recording based on data prevalence as a relevance criterion. Numerical examples across a synthetic and an ECG data set showcase the method's efficacy in discovering patterns. In a vehicle data set, 822 distinct dvb were identified, reducing data by $\SI{96.01}{\percent}$,  while relevant dvb remain included. Future research into selecting vehicle data based on multivariate time series using Behavior Forests and sharing them for faster trigger convergence shows promise for fleet coverage analysis, potentially integrating additional sensor modalities such as camera data analysis to enhance analysis capabilities.

§ ACKNOWLEDGMENT

This work results from the just better DATA (jbDATA)
project supported by the German Federal Ministry for Economic Affairs and Climate Action of Germany (BMWK) and the European Union, grant number 19A23003H.