# Counting the Numbers of Paths of all Lengths in Dendrimers and its
Applications

Hafsah Tabassum1,2 , Syed Ahtsham Ul Haq Bokhary3,
Thiradet Jiarasuksakun1,2, and Pawaton Kaemawichanurat1,2

1Mathematics and Statistics with Applications (MaSA),
2Department of Mathematics,
King Mongkut’s University of Technology Thonburi,
Bangkok, Thailand
3Bahauddin Zakariya University, Multan, Pakistan.
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Research supported by
Petchra Pra Jom Klao Ph.D. Research Scholarship from King Mongkut’s University
of Technology Thonburi (1281/2021).

###### Abstract

For positive integers $n$ and $k$, the dendrimer $T_{n,k}$ is defined as the
rooted tree of radius $n$ whose all vertices at distance less than $n$ from
the root have degree $k$. The dendrimers are higly branched organic
macromolecules having repeated iterations of branched units that surroundes
the central core. Dendrimers are used in a variety of fields including
chemistry, nanotechnology, biology. In this paper, for any positive integer
$\ell$, we count the number of paths of length $\ell$ of $T_{n,k}$. As a
consequence of our main results, we obtain the average distance of $T_{n,k}$
which we can establish an alternate proof for the Wiener index of $T_{n,k}$.
Further, we generalize the concept of medium domination, introduced by Vargör
and Dündar in 2011, of $T_{n,k}$.

Keywords: Dendrimer; Cayley Tree; Wiener Index; Average Distance; Medium
Domination
AMS subject classification: 05C05; 05C38; 05C30; 05C12; 05C69; 05C92

##  1 Introduction

The set of vertices in a graph $G=(V(G),E(G))$ is $V(G)$ while the set of
edges is denoted by $E(G)$. All graphs in this paper are finite and simple,
with no loops or multiple edges. The the set $\\{u:uv\in E(G)\\}$ is the
_neighbor set_ $N_{G}(v)$ of a vertex $v$ in $G$. The degree $deg_{G}(v)$ of a
vertex $v$ in $G$ is given by $|N_{G}(v)|$. If the subgraph of $G$ induced by
$S$ has no edges, then the vertex subset $S$ of $V(G)$ is _independent_. The
maximum cardinality of an independent set is given by the _independence
number_ of $G$ which denoted by $\alpha(G)$. If every vertex of $G$ has degree
$k$ then the graph $G$ is $k$_-regular_. For $u,v\in V(G)$, the length of a
shortest path from $u$ to $v$ is the _distance_ $d_{G}(u,v)$ between $u$ and
$v$ in $G$. The maximum distance between all pairs of vertices of $G$ is
_diameter_ $diam(G)$. The total of the distance between each pair of vertices
of $G$ divided by the number of pairs of vertices is the _average distance_
$\mu(G)$ of $G$. That is:

$\mu(G)=\frac{\displaystyle{\sum_{u,v\in
V(G)}d_{G}(u,v)}}{\displaystyle{\binom{|V(G)|}{2}}}.$

A _tree_ is a graph with no subgraphs that are cycles. A _leaf_ , also known
as _pendant vertex_ , is a vertex with degree one. A leaf’s incident edge is
the _pendant edge_ while a leaf’s neighbouring vertex is called a _support
vertex_. A _rooted tree_ $T$ is a tree whose one vertex identified as the root
$r$. Furthermore, if $d_{T}(r,v)=i$ a vertex $v$ of $T$ is at _level_ $i$ and
$T$ has $n$-_level_ if the greatest level of all vertices of $T$ is $n$. A
_balanced tree_ is a rooted tree with equal number of vertices at the same
level having the same degree. A _dendrimer_ $T_{n,k}$ is an $n$-level balanced
tree with the degree $k$ for all non-leaf vertices.A dendrimer is a molecule
with a well-defined chemical structure that is synthesised chemically.
Dendrimers have three key main components: one is the core, and it’s the most
fundamental aspect in dendrimer development, then branches that are added at
each step sequentially to produce a structure like tree, the last component is
end groups. Dendrimers are hyperbranched macromolecules that have a wide range
of applications in domains like supramolecular, drug development, and
nanotechnology. Some graph constants such as dominating numbers and some other
tpes of dominating number are used to describe a range of physical
characteristics, including physicochemical characteristics, thermodynamic
characters, chemical and biological actions, and so on. In 1978, Fritz
Vogtle’s was the first to bring these nanomolecules to researcher’s attention
[5]. In [2] the topological indices of well-known dendrimers were introduced.
Researchers have discovered topological indices for many chemical structures
such as dendrimers, trees and other graphs, inspired by the chemical relevance
of topological indices of molecular networks. In context of spectral graph
theory, the sum of the absolute values of the eigenvalues of the graph $G$ is
known as the _energy of graph_ $G$ which can be given as

$E(G)=\sum_{i=1}^{n}|\lambda_{i}|$

where $\lambda_{i},i=1,2,\dots,n$ are the eigenvalues of $G$. In [1], the
eigenvalues of the cayley tree dendrimers are obtained with the help of the
characteristic polynomials. The reduction formulas for calculating the
characteristic polynomials of d(2, k) and d(3, k) are constructed. Also, The
energy of the above mentioned dendrimers is calculated. For more studies in
dendrimers see [6, 26] for example.

The followings are examples of $T_{n,,k}$ when $n$ or $k$ is small. By the
definition of dendrimers, we have that $n\geq 1$ and $k\geq 2$.

When $n=1$, $T_{1,k}$ can be constructed by introducing $k$ vertices and
joining each of them to the central vertex through an edge. Thus $T_{1,k}$ is
a _star_ with $n+1$ vertices.

When $k=2$, $T_{n,2}$ is a _path_ consisting of $2n+1$ vertices.

When $n=2$, it can be observed that $T_{2,k}$ can be constructed from
$T_{1,k}$ by introducing $k-1$ vertices at each leaf of $T_{1,k}$ and then
joining them to that leaf. Hence, when $n,k\geq 2$, $T_{n,k}$ is constructed
from $T_{n-1,k}$ by introducing further $k-1$ vertices at each leaf vertex of
$T_{n-1,k}$ and then joining them to that leaf vertex. Namely, the procedure
of construction of $T_{n,k}$ for $(n\geq 2,k\geq 0)$ consists of $n$
iterations from the graph that has exactly one vertex.

Figure 1: The dendrimers $T_{3,4}$.

For a graph $G$, the sum of the distance between any pair of vertices of $G$
is known as the _Weiner index_ $W(G)$ of $G$. That is:

$W(G)=\displaystyle{\sum_{\\{u,v\\}\subseteq V(G)}d_{G}(u,v)}.$

In the quantitative structure-property relationships (QSPR) [3, 22, 25], the
Wiener index was the first and most well researched topological index. Since
then dozens of new indices have been developed to link topological indices
with various physical features. The boiling temperatures of alkane molecules
are closely associated with the Wiener index number, according to Wiener.
Later study on quantitative structure activity linkages revealed it is
connected with some other factors also such as the critical point parameters,
density, surface tension, viscosity of the liquid phase and the molecule’s van
der Waals surface area. It was originally called the path number since it was
defined as the total of the lengths between any two carbon atoms in an alkane
in terms of carbon-carbon bonds [29]. Wiener’s works did not make use of graph
theory, and the path number was only used in acyclic systems. Hosoya, [12] in
1971, was the first to define the _Wiener index_ within the context of
chemical graph theory. The Weiner index appears to have been studied for the
first time in the mathematical literature in 1976 [10]. This index has also
been referred to by the terms “graph distance” [10] and “transmission” [16,
23] uses the Laplacian matrix to introduce a graph-theoretical new definition
of the Wiener index for trees. Andrey A. Dobryin et. al. established the
Wiener index for Cayley tree dendrimer in [9] which states that for every
$k\geq 3$, the Wiener index of $T_{n,k}$ is

$\displaystyle
W(T_{n,k})=\frac{1}{(k-2)^{3}}[(k-1)^{2n}[nk^{3}-2(n+1)k^{2}+k]+2k^{2}(k-1)^{n}-k].$
(1)

For more studies of Weiner index see [14, 15] for example.

A graph $G$ fulfilling specific constraints can efficiently simulates numerous
scenarios in communication, facility locating, cryptology and other fields.
Due to cost constraint, it is frequently sought to have a spanning tree of $G$
that is optimal with respect to one or more attributes. One of these
attributes is usually the average distance between vertices. The average
distance in graph $G$ is defined as follows:

$\mu(G)=\frac{\sum_{\\{u,v\\}\subseteq V(G)}d_{G}(u,v)}{\binom{|V(G)|}{2}}$

The study of the average distance of graphs was initiated by Plesnik in his
classical result in [23]. The average distance is an important tool to analyse
entire structure of the graph. The parameter globally presents expected number
of edges that an object needs to travel between nodes (vertices) of networks.
This reflects data transmission efficiency of communication networks as well
as capability to deliver objects of transportation networks. Hence, the
average distance has been continuously studied in both theoretical, algorithm
and application areas. For example of the studies of average distance of
graphs, Fajtlowicz and Waller [11] established the inequality between the
average distance and the independence number in their classical paper since
1986 that $\alpha(G)\geq\mu(G)-1$ for every connected graph $G$. Chung [7]
improved this bound to bt $\alpha(G)\geq\mu(G)$ and further characterized that
the equality holds if and only if $G$ is a complete graph. For more studies of
the average distance of graphs see [8, 13, 27] for example.

Domination in graph has been extensively researched and utilised in a variety
of fields. Vargör and Dündar [28], established the idea of “the medium
domination number” which is defined as the total number of vertices that
dominate every pair of vertices with the average value of it. In the same way
each vertex in a graph may protect every vertex in its immediate surroundings
and in domination every vertex in neighborhood must be secured. In any
connected simple graph $G$ having order $n$, the medium domination number of
$G$ is defined as $\gamma_{m}(G)=\frac{TDT(G)}{{n\choose 2}}$. The medium
domination number of Jahangir graph was determind by Ramachandran and Parvathi
[24]. Mirajkar et. al. found the medium domination number of few poly
silicates in [17]. Mahadevan et.al. proposed the concept of the Extended
Medium Domination number of a graph in [20]. The total number of vertices that
dominate each pair of vertices

$ETDV(G)=\sum edom(u,v)$

for any $u,v\in V(G)$. The extended medium domination number of a graph $G$ is
defined as $EMD(G)=\frac{EDT(G)}{{n\choose 2}}$. $ETDV(G)$ is the sum of
number of path of length one,two and three. Motivated by the above G.
Mahadevan et.al. introduced the idea of Double Twin domination of a graph [20]
The total number of vertices that dominate every pair of vertices

$SDTwin(G)=\sum DTwin(u,v)$

for $u,v\in V(G)$. In any simple graph $G$ with $n$ number of vertices, the
double Twin domination number of $G$ can be given as
$DTD(G)=\frac{SDTwin(G)}{{n\choose 2}}$ where $SDTwin(G)$ is the total of
number of path having length one, two, three and four. This number was
discovered by Mahadevan and Vijayalakshmi in [21], for variety of common
classes of graphs like path, cycle, wheel graph, complete graph, star graph,
Cartesian product of path and Corona product of path.

From the above discussion, it can be showed that the average distance and the
medium domination number of dendrimers can be found if we know the number of
paths of all lengths. Thus, the problems that arises is:

###### Problem 1

For non-negative integers $n,k$ and $\ell$, how many paths of length $\ell$
does a dendrimer $T_{n,k}$ have?

Surprisingly, to the best of our knowledge, Problem 1 has not been answered.

In this paper, we solve Problem 1 by establishing the exact and recursive
formulas to count the number of paths of length $\ell$ of $T_{n,k}$ for all
$1\leq\ell\leq 2n$. As a consequence, we easily obtain average distance of
$T_{n,k}$. Further, we generalize the concept of medium domination to
$\ell$-medium domination in graphs.

##  2 Main Results and Applications

In this section, we state our main results of this paper as well as their
applications in Subsections 2.1 and 2.2 while most of the proofs are given in
Section 4. First, for a graph $G$, we let

$n_{\ell}(G)$: the number of paths of length $\ell$ of $G$.

The first main result is the formula of $n_{\ell}(T_{n,k})$ for all possible
values of $\ell$. Recall that when $k=2$, the dendrimer $T_{n,2}$ is a path of
length $2n$. Thus, we let $x_{1},...,x_{2n+1}$ be $T_{n,2}$. Clearly, for a
positive integer $1\leq\ell\leq 2n$, all the paths of length $\ell$ are
$x_{i},x_{i+1},...,x_{i+\ell}$ for all $1\leq i\leq 2n+1-\ell$. Hence, we
obtain the following observation.

###### Observation 1

Let $T_{n,k}$ be the dendrimer. If $k=2$, then

$n_{\ell}(T_{n,2})=2n+1-\ell.$

Thus, throughout of this paper, we may assume that $k\geq 3$. Further, for a
tree $T$, we let

$n^{1}_{\ell}(T):$ the number of paths of length $\ell$ of $T$ with exactly
one end vertex is a leaf of $T$.

$n^{2}_{\ell}(T):$ the number of paths of length $\ell$ of $T$ whose both end
vertices are leaves of $T$.

Our main results in this subsection are Theorem 1, Corollaries 1 and 2. As
informed earlier, the proofs are given in Section 4.

###### Theorem 1

Let $T_{n,k}$ be the dendrimer and $k\geq 3$. If $\ell$ is even number, then

$n_{\ell}(T_{n,k})=(k-1)n^{1}_{\ell-1}(T_{n-1,k})+(k-1)^{2}n^{2}_{\ell-2}(T_{n-1,k})+n_{\ell}(T_{n-1,k}).$

If $\ell$ is odd number, then

$n_{\ell}(T_{n,k})=(k-1)n^{1}_{\ell-1}(T_{n-1,k})+2(k-1)n^{2}_{\ell-1}(T_{n-1,k})+n_{\ell}(T_{n-1,k}).$

By Theorem 1, we obtain the following corollaries. It is worth noting that
Corollary 2 is a combinatorial identity which is obtained by the counting two
way principle.

###### Corollary 1

Let $T_{n,k}$ be the dendrimer and $k\geq 3$. Then

$n_{\ell}(T_{n,k})=\left\\{\begin{array}[]{rl}\frac{k(k-1)^{\ell-1}}{2}[\frac{k(k-1)^{n-\frac{\ell}{2}}-2}{k-2}]&\text{when
}\ell\textnormal{ is even},\\\\[15.0pt]
k(k-1)^{\frac{\ell-1}{2}}[\frac{(k-1)^{n}-(k-1)^{\frac{\ell-1}{2}}}{k-2}]&\text{when
}\ell\textnormal{ is odd.}\end{array}\right.$

###### Corollary 2

For natural number $n$ and $k$ such that $k\geq 3$, we have that

$\binom{1+\frac{k[(k-1)^{n}-1]}{k-2}}{2}=\sum^{n-1}_{\ell=0}k(k-1)^{\ell}[\frac{(k-1)^{n}-(k-1)^{\ell}}{k-2}]+\sum^{n}_{\ell=1}\frac{k(k-1)^{2\ell-1}}{2}[\frac{k(k-1)^{n-l}-2}{k-2}]$

###  2.1 Wiener Index and Average Distance

In this subsection,We have linked our main problem to distance in Cayaley Tree
Dendrimer. Using the results obtained in Theorem 1, Corollary 1 and 2, we have
found the Wiener index and average distance of $T_{n,k}$. We obtain
Corollaries 3 and 4. However, we may need Theorem 2 and the proof of this
theorem is given in Section 4.

###### Theorem 2

Let $T$ be a tree having the diameter $diam(T)$. Then

$\displaystyle{\sum_{\\{u,v\\}\subseteq
V(T)}d_{T}(u,v)}=\displaystyle{\sum^{diam(T)}_{\ell=1}\ell n_{\ell}(T)}.$

By Corollary 1, we have that

$\displaystyle\displaystyle{\sum^{2n}_{\ell=1}\ell n_{\ell}(T_{n,k})}=$
$\displaystyle\sum^{n-1}_{l=0}(2l+1)k(k-1)^{l}[\frac{(k-1)^{n}-(k-1)^{l}}{k-2}]+$
$\displaystyle\sum^{n}_{l=1}(2l)\frac{k(k-1)^{2l-1}}{2}[\frac{k(k-1)^{n-l}-2}{k-2}].$
(2)

As $diam(T_{n,k})=2n$, by (2.1) and Theorem 2, we immediately obtain the
following corollaries.

###### Corollary 3

Let $T_{n,k}$ be the dendrimer with the Weiner index $W(T_{n,k})$. Then

$W(T_{n,k})=\sum^{n-1}_{l=0}(2l+1)k(k-1)^{l}[\frac{(k-1)^{n}-(k-1)^{l}}{k-2}]+\sum^{n}_{l=1}(2l)\frac{k(k-1)^{2l-1}}{2}[\frac{k(k-1)^{n-l}-2}{k-2}].$

It is worth noting that the right hand side of the equation in Corollary 3 can
be simplified to Equation (1).

###### Corollary 4

Let $T_{n,k}$ be the dendrimer with the average distance $\mu(T_{n,k})$. Then

$\mu(T_{n,k})=\frac{\sum^{n-1}_{l=0}(2l+1)k(k-1)^{l}[\frac{(k-1)^{n}-(k-1)^{l}}{k-2}]+\sum^{n}_{l=1}(2l)\frac{k(k-1)^{2l-1}}{2}[\frac{k(k-1)^{n-l}-2}{k-2}]}{\displaystyle{\binom{1+\frac{k[(k-1)^{n}-1]}{k-2}}{2}}}.$

###  2.2 Medium Domination

Motivated by [20, 21, 28], we generalize their results to $\varsigma$-medium
domination of $T_{n,k}$. For a graph $G$ of order $n$ and for some
$2\leq\varsigma\leq diam(G)$, the $\varsigma$_-medium domination number_
$\gamma_{\varsigma MD}(G)$ of $G$ is defined as

$\gamma_{\varsigma MD}(G)=\frac{\varsigma(G)}{{n\choose 2}}$

where

$\varsigma(G)=\sum^{\varsigma}_{\ell=1}n_{\ell}(G),$

the sum of all paths whose lengths less than or equal to $\varsigma$. Hence,
when $G$ is a dendrimer $T_{n,k}$, we obtain the $\varsigma$-medium domination
number of $T_{n,k}$ as follow:

###### Corollary 5

Let $T_{n,k}$ be the dendrimer with the $\varsigma$-medium domination number
$\gamma_{\varsigma MD}(G)$. Then

$\gamma_{\varsigma MD}(T_{n,k})=\frac{\varsigma(T_{n,k})}{{|V(T_{n,k})|\choose
2}}$

where

$\displaystyle\varsigma(T_{n,k})=\sum^{s}_{\ell=0}k(k-1)^{\ell}[\frac{(k-1)^{n}-(k-1)^{\ell}}{k-2}]+\sum^{\lfloor\frac{\varsigma}{2}\rfloor}_{\ell=1}\frac{k(k-1)^{2\ell-1}}{2}[\frac{k(k-1)^{n-\ell}-2}{k-2}]$

and

$s=\left\\{\begin{array}[]{rl}\lfloor\frac{\varsigma}{2}\rfloor&\text{when
}\varsigma\textnormal{ is odd},\\\\[15.0pt]
\lfloor\frac{\varsigma}{2}\rfloor-1&\text{when }\varsigma\textnormal{ is
even.}\end{array}\right.$

##  3 Preliminaries

In this section, we provide some results hat are used in establishing our main
theorems. We begin with a simple but yet useful formula for geometric series.
For a geometric series $S_{n}=a+ar+ar^{2}+\cdots+ar^{n-1}$, we have that

$S_{n}=\sum^{n-1}_{i=0}ar^{i}=\frac{a(1-r^{n})}{1-r}$

where $n$ is the number of terms, $a$ is the coefficient and $r\neq 1$ is the
common ratio.

Further, for $T_{n,k}$, we may have the following formulas by simple counting
arguments and geometric series,

the total number of vertices of degree $k$ are $\frac{k(k-1)^{n-1}-2}{k-2}$,

the total number of vertices of degree 1 (i.e. pendent vertices) is equal to
$k(k-1)^{n-1}$,

the total number of vertices is equal to $1+\frac{k[(k-1)^{n}-1]}{k-2}$,

and

the total number of edges is equal to $\frac{k[(k-1)^{n}-1]}{k-2}$.

##  4 Proofs

In this section, we give the proofs of Theorem 1, Corollary 1, Corollary 2 and
Theorem 2.

###  4.1 Proof of Theorem 1

To prove this theorem, we need to establish Lemmas 1 and 2 which are the exact
formulas of $n^{1}_{\ell}(T_{n,k})$ and $n^{2}_{\ell}(T_{n,k})$.

###### Lemma 1

for $n,k\geq 1$ and $1\leq\ell\leq 2n$, we let $n^{1}_{\ell}(T_{n,k})$ be the
number of paths of length $\ell$ of $T_{n,k}$ having exactly one end vertex as
a leaf of $T_{n,k}$. Then

$n^{1}_{\ell}(T_{n,k})=\left\\{\begin{array}[]{rl}k(k-1)^{n+\frac{\ell}{2}-2}&\text{when
}\ell\textnormal{ is even},\\\\[15.0pt]
k(k-1)^{n+\frac{\ell-1}{2}-1}&\text{when }\ell\textnormal{ is
odd.}\end{array}\right.$

Proof. First, we let $r$ be the root and let $x$ be an arbitrary leaf of the
graph $T_{n,k}$. Further, for $0\leq j\leq n$, we let

$L_{j}:$ the set of all vertices of $T_{n,k}$ at distance $i$ from $r$,

and

$\mathcal{P}_{x}:$ the family of all paths of $T_{n,k}$ starting from $x$ and
the other end vertex is not
a leaf of $T_{n,k}$.

We distinguish two cases according to the value of $\ell$.

Case 1: $1\leq\ell\leq n$.

For a path $P\in\mathcal{P}_{x}$, we let

$min(P)=\min\\{j:V(P)\cap L_{j}\neq\emptyset\\}$.

Further, for $0\leq i\leq\lfloor\frac{\ell-1}{2}\rfloor$, we let

$\mathcal{P}_{x,i}=\\{P\in\mathcal{P}_{x}:min(P)=n-\ell+i\\}$.

It can be observed that
$\mathcal{P}_{x,0},\mathcal{P}_{x,1},...,\mathcal{P}_{x,\lfloor\frac{\ell-1}{2}\rfloor}$
partition $\mathcal{P}_{x}$.

When $i=0$, we have that $|\mathcal{P}_{x,0}|=1$ as there is exactly one path
of length $\ell$ starting from $x$, goes through vertices in
$L_{n-1},L_{n-2},...,L_{n-\ell+1}$ and terminates in $L_{n-\ell}$.

For each $1\leq i\leq\lfloor\frac{\ell-1}{2}\rfloor$, all the paths in
$\mathcal{P}_{x,i}$ start from $x$ and go trough vertices in
$L_{n-1},...,L_{n-\ell+i+1},L_{n-\ell+i}$ with exactly one possibility. We may
let $y\in L_{n-\ell+i+1}$ and $z\in L_{n-\ell+i}$ be the vertices that are in
all the paths. Then, from the vertex $z$, all the paths move back to
$L_{n-\ell+i+1},...,L_{n-\ell+2i}$. As $y$ is already in every of such path,
there are $k-2$ possibilities for all the paths in $P_{x,i}$. Further, there
are $k-1$ possibilities for all the paths to pass each of
$L_{n-\ell+i+2},...,L_{n-\ell+2i}$. Hence,

$\displaystyle|\mathcal{P}_{x,i}|=(k-2)(k-1)^{i-1}$

which implies that

$\displaystyle|\mathcal{P}_{x}|$
$\displaystyle=|\mathcal{P}_{x,0}|+|\mathcal{P}_{x,1}|+\cdots+|\mathcal{P}_{x,\lfloor\frac{\ell-1}{2}\rfloor}|$
$\displaystyle=1+(k-2)+(k-2)(k-1)+\cdots+(k-2)(k-1)^{\lfloor\frac{\ell-3}{2}\rfloor}.$

After simplifying this geometric series, we get

$|\mathcal{P}_{x}|=(k-1)^{\lfloor\frac{\ell-1}{2}\rfloor}$

and this proves Case 1.

Case 2: $\ell=n+1\leq l\leq 2n$.

In this case, we let

$\mathcal{R}_{x}=\\{P\in\mathcal{P}_{x}:r\in V(P)\\}$

and

$\mathcal{S}_{x}=\\{P\in\mathcal{P}_{x}:r\notin V(P)\\}$.

We first count the number of paths in $\mathcal{R}_{x}$. All the paths in
$\mathcal{R}_{x}$ start from $x$ and pass to the root $r$ with one
possibilities. Then, from $r$, all the paths pass trough
$L_{1},...,L_{\ell-n-1}$ and terminate in $L_{\ell-n}$, each of which with the
possibilities $k-1$. Thus, $|\mathcal{R}_{x}|=(k-1)^{\ell-n}$.

Next, we count the number of paths in $\mathcal{S}_{x}$ by similar arguments
as in Case 1. For $\ell-n+1\leq i\leq\lfloor\frac{\ell-1}{2}\rfloor$, we let

$\mathcal{S}_{x,i}=\\{P\in\mathcal{S}_{x}:min(P)=n-\ell+i\\}$.

Clearly,
$\mathcal{S}_{x,\ell-n+1},...,\mathcal{S}_{x,\lfloor\frac{\ell-1}{2}\rfloor}$
partitions $\mathcal{S}_{x}$.

For each $\ell-n+1\leq i\leq\lfloor\frac{\ell-1}{2}\rfloor$, all paths in
$\mathcal{S}_{x,i}$ start from $x$ pass trough $L_{n-1},...,L_{n-\ell+i+1}$ to
$L_{n-\ell+i}$ with one possibility. Then, the paths pass back to
$L_{n-\ell+i+1}$ with $k-2$ possibilities and continue in $L_{n-\ell+i+2}$
until terminating in $L_{n-\ell+2i}$, each of which with $k-1$ possibilities.
Thus

$\displaystyle|\mathcal{S}_{x,i}|=(k-2)(k-1)^{i-1}$

which implies that

$\displaystyle|S_{x}|$
$\displaystyle=|\mathcal{S}_{x,\ell-n+1}|+\cdots+|\mathcal{S}_{x,\lfloor\frac{\ell-1}{2}\rfloor}|$
$\displaystyle=(k-2)(k-1)^{\ell-n}+(k-2)(k-1)^{\ell-n+1}+\cdots+(k-2)(k-1)^{\lfloor\frac{\ell-3}{2}\rfloor}$
$\displaystyle=(k-2)\Big{(}\frac{(k-1)^{\lfloor\frac{\ell-1}{2}\rfloor}-1}{k-2}-\frac{(k-1)^{\ell-n}-1}{k-2}\Big{)}$
$\displaystyle=(k-1)^{\lfloor\frac{\ell-1}{2}\rfloor}-(k-1)^{\ell-n}.$

Hence,

$\displaystyle|\mathcal{P}_{x}|=|\mathcal{R}_{x}|+|\mathcal{S}_{x}|=(k-1)^{\lfloor\frac{\ell-1}{2}\rfloor}$

and this proves Case 2.

In both cases, we have that
$|\mathcal{P}_{x}|=(k-1)^{\lfloor\frac{\ell-1}{2}\rfloor}$. As $x$ is an
arbitrary leaf of $T_{n,k}$ and $T_{n,k}$ has $k(k-1)^{n-1}$ leaves, it
follows that

$n^{1}_{\ell}(T_{n,k})=\left\\{\begin{array}[]{rl}k(k-1)^{n+\frac{\ell}{2}-2}&\text{when
}\ell\textnormal{ is even},\\\\[15.0pt]
k(k-1)^{n+\frac{\ell-1}{2}-1}&\text{when }\ell\textnormal{ is
odd}\end{array}\right.$

and this proves Lemma 1. $\Box$

###### Lemma 2

Let $n^{2}_{\ell}(T_{n,k})$ be the number of paths of length $\ell$ that
starts and end on a leaf vertex of the graph $T_{n,k}$. Then, for $n,k\geq 1$,

$n^{2}_{\ell}(T_{n,k})=\left\\{\begin{array}[]{rl}k(k-1)^{n+\frac{\ell}{2}-3}\binom{k-1}{2}&\text{when
}2\leq\ell\leq 2n-2\\\\[15.0pt] (k-1)^{\ell-2}\binom{k}{2}&\text{when
}\ell=2n.\end{array}\right.$

Proof. First, we let

$\mathcal{Q}_{\ell}:$ the family of paths of length $\ell$ of $T_{n,k}$ whose
both end vertices are leaves of $T_{n,k}$.

Clearly, $\ell$ must be even. For a path $P\in\mathcal{Q}_{\ell}$, we let
$x_{P}$ be the center of $P$ which the distance from $x_{p}$ to the end
vertices of $P$ are both equal to $\frac{\ell}{2}$. We distinguish $2$ cases
according to the value of $\ell$.

Case 1: $2\leq\ell\leq 2n-2$.

It can be observed that every path in $\mathcal{Q}_{\ell}$ has the center in
$L_{n-\frac{\ell}{2}}$. Let $x$ be a vertex in $L_{n-\frac{\ell}{2}}$. There
are $k-1$ neighbors of $x$ in $L_{n-\frac{\ell}{2}+1}$. Each pair of these
$k-1$ neighbors can be passed by a path in $\mathcal{Q}_{\ell}$. Hence, there
are $\binom{k-1}{2}$ possibilities for the paths in $\mathcal{Q}_{\ell}$. We
may let $x_{1}$ and $x_{2}$ be a pair among these $\binom{k-1}{2}$
possibilities. There are $(k-1)^{\frac{\ell}{2}-1}$ paths from each of $x_{1}$
and $x_{2}$ to the leaves of $T_{n,k}$. Hence, there are

$\binom{k-1}{2}(k-1)^{\frac{\ell}{2}-1}(k-1)^{\frac{\ell}{2}-1}=(k-1)^{\ell-2}\binom{k-1}{2}$

paths whose center is $x$ and both end vertices are leaves. Since $x$ is
arbitraty and there are $k(k-1)^{n-\frac{\ell}{2}-1}$ vertices in
$L_{n-\frac{\ell}{2}}$, it follows that

$\displaystyle
n^{2}_{\ell}(T_{n,k})=|\mathcal{Q}_{\ell}|=k(k-1)^{n-\frac{\ell}{2}-3}\binom{k-1}{2}.$

Case 2: $\ell=2n$

In this case, the root $r$ is the center of all paths in $\mathcal{Q}_{2n}$.
There are $\binom{k}{2}$ possibilities for the paths in $\mathcal{Q}_{2n}$ to
pass these vertices. Similarly, we let $x_{1}$ and $x_{2}$ be a pair among
these $\binom{k}{2}$ possibilities. There are $(k-1)^{\frac{\ell}{2}-1}$ paths
from each of $x_{1}$ and $x_{2}$ to the leaves of $T_{n,k}$. Hence,

$n^{2}_{\ell}(T_{n,k})=|\mathcal{Q}_{2n}|=(k-1)^{\ell-2}\binom{k}{2}$

and this proves Lemma 2. $\Box$

Now we are ready to prove Theorem 1.

Proof of Theorem 1 Recall that the graph $T_{n,k}$ can be constructed from
$T_{n-1,k}$ by introducing $k-1$ vertices to each leaf, and joining these
$k-1$ vertices to the leaf. We have considered two cases.

Case 1: $\ell$ is an even number.

Every path of length $\ell$ in this case is either (_i_) lies completely in
$T_{n-1,k}$, (_ii_) can be formed from a path of length $\ell-1$ whose exactly
one end vertex is a leaf of $T_{n-1,k}$ or (_iii_) can be formed from a path
of length $\ell-2$ whose both end vertices are at the leaves of $T_{n-1,k}$.
The Case (_i_) gives $n_{\ell}(T_{n-1,k})$ paths of length $\ell$ while the
Case (_ii_) gives $(k-1)n^{1}_{\ell}(T_{n-1,k})$ paths of length $\ell$ as the
end vertex at a leaf of $T_{n-1,k}$ can be extended with $k-1$ ways. Finally,
the Case (_iii_) gives $(k-1)^{2}n^{2}_{\ell-2}(T_{n-1,k})$ paths as every
path of length $\ell-2$ whose both end vertices are at the leaves of
$T_{n-1,k}$ can be extended to the path of length $\ell$ by $(k-1)^{2}$ ways,
$k-1$ for each end vertex. Thus, we have the following recursive formula

$n_{\ell}(T_{n,k})=(k-1)n^{1}_{\ell-1}(T_{n-1,k})+(k-1)^{2}n^{2}_{\ell-2}(T_{n-1,k})+n_{\ell}(T_{n-1,k}).$

This proves Case 1.

Case 2: $\ell$ is an odd number

Similarly, every path of length $\ell$ in this case is either (_i_) lies
completely in $T_{n-1,k}$, (_ii_) can be formed from a path of length $\ell-1$
whose exactly one end vertex is a leaf of $T_{n-1,k}$ or (_iii_) can be formed
from a path of length $\ell-1$ whose both end vertices are at the leaves of
$T_{n-1,k}$. The Case (_i_) gives $n_{\ell}(T_{n-1,k})$ paths while the Case
(_ii_) gives $(k-1)n^{1}_{\ell}(T_{n-1,k})$ paths. For the Case (_iii_), we
can only extend these paths of length $\ell-1$ in $T_{n-1,k}$ to be a path of
length $\ell$ by extending only one end vertex, $k-1$ ways for each end
vertex. Thus there are $2(k-1)n^{2}_{\ell-1}(T_{n-1,k})$ paths in this case.
Thus, we have a recursive formula

$n_{\ell}(T_{n,k})=(k-1)n^{1}_{\ell-1}(T_{n-1,k})+2(k-1)n^{2}_{\ell-1}(T_{n-1,k})+n_{\ell}(T_{n-1,k}).$

This proves Case 2 and completes the proof of our theorem. $\Box$

###  4.2 Proof of Corollary 1

We distinguish two cases according to the parity of $\ell$.

Case 1: $\ell$ is an even number.

By Theorem 1, we have that

$\displaystyle n_{\ell}(T_{n,k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{n-1,k})+(k-1)^{2}n^{2}_{\ell-2}(T_{n-1,k})+n_{\ell}(T_{n-1,k})$
$\displaystyle n_{\ell}(T_{n-1,k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{n-2,k})+(k-1)^{2}n^{2}_{\ell-2}(T_{n-2,k})+n_{\ell}(T_{n-2,k})$
$\displaystyle n_{\ell}(T_{n-2,k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{n-3,k})+(k-1)^{2}n^{2}_{\ell-2}(T_{n-3,k})+n_{\ell}(T_{n-3,k})$
$\displaystyle\vdots$ $\displaystyle n_{\ell}(T_{\frac{\ell}{2}+1,k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{\frac{\ell}{2},k})+(k-1)^{2}n^{2}_{\ell-2}(T_{\frac{\ell}{2},k})+n_{\ell}(T_{\frac{\ell}{2},k})$
$\displaystyle n_{\ell}(T_{\frac{\ell}{2},k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{\frac{\ell-2}{2},k})+(k-1)^{2}n^{2}_{\ell-2}(T_{\frac{\ell-2}{2},k})+n_{\ell}(T_{\frac{\ell-2}{2},k}).$

As $\frac{\ell-2}{2}<\frac{\ell}{2}$, we have
$n_{\ell}(T_{\frac{\ell-2}{2},k})=0$. Further,
$n^{1}_{\ell-1}(T_{\frac{\ell-2}{2},k})=0$ because
$\frac{\ell-2}{2}<\frac{\ell-1}{2}$. Thus, summing the above equations we have

$n_{\ell}(T_{n,k})=(k-1)\sum^{n-1}_{i=\frac{\ell}{2}}{n^{1}_{\ell-1}(T_{i,k})}+(k-1)^{2}\sum^{n-1}_{j=\frac{\ell-2}{2}}{n^{2}_{\ell-2}(T_{j,k})}.$
(3)

By Lemma 1 when $\ell-1$ is odd, we have that

$\displaystyle\sum^{n-1}_{i=\frac{\ell}{2}}{n^{1}_{\ell-1}(T_{i,k})}$
$\displaystyle=\sum^{n-1}_{i=\frac{\ell}{2}}{k(k-1)^{i+\frac{\ell-2}{2}-1}}$
$\displaystyle=k(k-1)^{\frac{\ell}{2}-2}[\sum^{n-1}_{i=0}{(k-1)^{i}}-\sum^{\frac{\ell}{2}-1}_{i=0}{(k-1)^{i}}].$

By Geometric Series, we have that

$\sum^{n-1}_{i=\frac{\ell}{2}}{n^{1}_{\ell-1}(T_{i,k})}=k(k-1)^{\frac{\ell}{2}-2}[\frac{(k-1)^{n}-(k-1)^{\frac{\ell}{2}}}{k-2}].$
(4)

For the sum $\sum^{n-1}_{j=\frac{\ell-2}{2}}{n^{2}_{\ell-2}(T_{j,k})}$, we may
split the first term as

$\sum^{n-1}_{j=\frac{\ell-2}{2}}{n^{2}_{\ell-2}(T_{j,k})}=n^{2}_{\ell-2}(T_{\frac{\ell-2}{2},k})+\sum^{n-1}_{j=\frac{\ell}{2}}{n^{2}_{\ell-2}(T_{j,k})}.$

By Lemma 2, we have that

$\displaystyle\sum^{n-1}_{j=\frac{\ell-2}{2}}{n^{2}_{\ell-2}(T_{j,k})}$
$\displaystyle=(k-1)^{\ell}{k\choose
2}+\sum^{n-1}_{j=\frac{\ell}{2}}{k(k-1)^{\frac{\ell}{2}-4+j}}{k-1\choose 2}$
$\displaystyle=(k-1)^{\ell}{k\choose 2}+k(k-1)^{\frac{\ell}{2}-4}{k-1\choose
2}\sum^{n-1}_{j=\frac{\ell}{2}}(k-1)^{j}.$

By Geometric Series, we have that

$\sum^{n-1}_{j=\frac{\ell-2}{2}}{n^{2}_{\ell-2}(T_{j,k})}=(k-1)^{\ell-4}{k\choose
2}+k(k-1)^{\frac{\ell}{2}-4}{k-1\choose
2}[\frac{(k-1)^{n}-(k-1)^{\frac{\ell}{2}}}{k-2}].$ (5)

Putting values from Equation (4) and (5) into Equation (3) and simplifying, we
get

$n_{\ell}(T_{n,k})=\frac{k(k-1)^{\ell-1}}{2}[\frac{k(k-1)^{n-\frac{\ell}{2}}-2}{k-2}].$
(6)

This proves Case 1.

Case 2: $\ell$ is an odd number

By Theorem 1, we have that

$\displaystyle n_{\ell}(T_{n,k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{n-1,k})+2(k-1)n^{2}_{\ell-1}(T_{n-1,k})+n_{\ell}(T_{n-1,k})$
$\displaystyle n_{\ell}(T_{n-1,k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{n-2,k})+2(k-1)n^{2}_{\ell-1}(T_{n-2,k})+n_{\ell}(T_{n-2,k})$
$\displaystyle n_{\ell}(T_{n-2,k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{n-3,k})+2(k-1)n^{2}_{\ell-1}(T_{n-3,k})+n_{\ell}(T_{n-3,k})$
$\displaystyle\vdots$ $\displaystyle n_{\ell}(T_{\frac{\ell+1}{2},k})$
$\displaystyle=(k-1)n^{1}_{\ell-1}(T_{\frac{\ell-1}{2},k})+2(k-1)n^{2}_{\ell-1}(T_{\frac{\ell-1}{2},k})+n_{\ell}(T_{\frac{\ell-1}{2},k}).$

Since $\frac{\ell-1}{2}<\frac{\ell}{2}$, it follows that
$n_{\ell}(T_{\frac{\ell-1}{2},k})=0$. Further,
$n^{1}_{\ell-1}(T_{\frac{\ell-1}{2},k})=0$ because every path of length
$\ell-1$ always has both end vertices at leaves of $T_{\frac{\ell-1}{2},k}$.
Thus, summing the above equations we have

$n_{\ell}(T_{n,k})=(k-1)\sum^{n-1}_{i=\frac{\ell+1}{2}}{n^{1}_{\ell-1}(T_{i,k})}+2(k-1)\sum^{n-1}_{j=\frac{\ell+1}{2}}{n^{2}_{\ell-1}(T_{j,k})}+2(k-1){n^{2}_{\ell-1}}(T_{\frac{\ell-1}{2},k}).$
(7)

By Lemma 1 when $\ell-1$ is even, we have that

$\displaystyle\sum^{n-1}_{i=\frac{\ell+1}{2}}{n^{1}_{\ell-1}(T_{i,k})}$
$\displaystyle=\sum^{n-1}_{i=\frac{\ell+1}{2}}{k(k-1)^{i+\frac{\ell-1}{2}-2}}$
$\displaystyle=k(k-1)^{\frac{\ell-1}{2}-2}\sum^{n-1}_{i=\frac{\ell+1}{2}}{(k-1)^{i}}$
$\displaystyle=k(k-1)^{\frac{\ell-1}{2}-2}[\sum^{n-1}_{i=0}{(k-1)^{i}}-\sum^{\frac{\ell-1}{2}}_{i=0}{(k-1)^{i}}].$

Hence, we have by Geometric Series that

$\sum^{n-1}_{i=\frac{\ell+1}{2}}{n^{1}_{\ell-1}(T_{i,k})}=k(k-1)^{\frac{\ell-1}{2}-2}[\frac{(k-1)^{n}-(k-1)^{\frac{\ell+1}{2}}}{k-2}].$
(8)

Further, we have by Lemma 2 that

$\displaystyle\sum^{n-1}_{j=\frac{\ell+1}{2}}{n^{2}_{\ell-1}(T_{j,k})}$
$\displaystyle=\sum^{n-1}_{j=\frac{\ell+1}{2}}k(k-1)^{\frac{\ell+1}{2}-2+j}{k-1\choose
2}$ $\displaystyle=k(k-1)^{\frac{\ell+1}{2}-2}{k-1\choose
2}\sum^{n-1}_{j=\frac{\ell+1}{2}}(k-1)^{j}.$

We have by Geometric Series that

$\sum^{n-1}_{j=\frac{\ell+1}{2}}{n^{2}_{\ell-1}(T_{j,k})}=k(k-1)^{\frac{\ell+1}{2}-2}{k-1\choose
2}[\frac{(k-1)^{n}-(k-1)^{\frac{\ell+1}{2}}}{k-2}].$ (9)

Putting values from Equations (8) and (9) into Equation (7) and simplifying,
we get

$n_{\ell}(T_{n,k})=k(k-1)^{\frac{\ell-1}{2}}[\frac{(k-1)^{n}-(k-1)^{\frac{\ell-1}{2}}}{k-2}].$
(10)

This proves Case 2 and completes the proof of Corollary 1. $\Box$

###  4.3 Proof of Corollary 2

We let $\binom{V(T_{n,k})}{2}$ be the set of all sets of two vertices of
$T_{n,k}$. Namely,

$\displaystyle\binom{V(T_{n,k})}{2}=\\{\\{u,v\\}:u,v\in V(T_{n,k})\\}$

and

$\displaystyle\Big{|}\binom{V(T_{n,k})}{2}\Big{|}=\binom{|V(T_{n,k})|}{2}=\binom{1+\frac{k[(k-1)^{n}-1]}{k-2}}{2}.$

Construct the $(0,1)$-matrix whose rows are the pairs $\\{u,v\\}$ of
$\binom{V(T_{n,k})}{2}$, columns are the path length $\ell$ for all
$1\leq\ell\leq 2n$ and the entries $a_{\\{u,v\\},\ell}$ are defined as
follows:

$a_{\\{u,v\\},\ell}=\left\\{\begin{array}[]{rl}1&\text{if
}d_{T}(u,v)=\ell,\\\\[15.0pt] 0&\text{otherwise.}\end{array}\right.$

We first consider Row $\\{u,v\\}$. There is exactly one column, $\ell$ say,
such that

$a_{\\{u,v\\},\ell}=1$

but

$a_{\\{u,v\\},j}=0$

for all $j\in\\{1,...,2n\\}\setminus\\{\ell\\}$. Thus, the summation of all
entries in this matrix is

$\displaystyle\sum_{\\{u,v\\}\subseteq
V(T)}1=\Big{|}\binom{V(T_{n,k})}{2}\Big{|}=\binom{1+\frac{k[(k-1)^{n}-1]}{k-2}}{2}.$

We then consider Column $\ell$. By the definition of $n_{\ell}(T_{n,k})$,
there are $n_{\ell}(T_{n,k})$ rows whose entries are equal to $1$ while the
entries of the other rows are all $0$. Hence, the summation of all entries of
Column $\ell$ is equal to $n_{\ell}(T)$ implying that the summation of all
etries in this matrix is $\sum^{2n}_{\ell=1}n_{\ell}(T)$.

By the counting two way principle, we have that

$\binom{1+\frac{k[(k-1)^{n}-1]}{k-2}}{2}=\sum^{2n}_{\ell=1}n_{\ell}(T_{n,k}).$

This proves Corollary 2.

###  4.4 Proof of Theorem 2

We prove this theorem by similar argument as in the proof of Corollary 2.
First, we let $T$ be a tree with the diameter $diam(T)=t$. We let
$\binom{V(T)}{2}$ be the set of all sets of two vertices of $T$. Construct the
matrix whose rows are the pairs $\\{u,v\\}$ of $\binom{V(T)}{2}$, columns are
the path length $\ell$ for all $1\leq\ell\leq t$ and the entries
$a_{\\{u,v\\},\ell}$ are defined as follows:

$a_{\\{u,v\\},\ell}=\left\\{\begin{array}[]{rl}\ell&\text{if
}d_{T}(u,v)=\ell,\\\\[15.0pt] 0&\text{otherwise.}\end{array}\right.$

Thus, in the Column $j$, all the entries are either $j$ or $0$.

We first consider Row $\\{u,v\\}$. There is exactly one column, $\ell$ say,
such that

$a_{\\{u,v\\},\ell}=\ell=d_{T}(u,v)$

but

$a_{\\{u,v\\},j}=0$

for all $j\in\\{1,...,t\\}\setminus\\{\ell\\}$. Thus, the summation of all
entries of Row $\\{u,v\\}$ is equal to $\ell=d_{T}(u,v)$ implying that the
summation of all entries in this matrix is $\sum_{\\{u,v\\}\subseteq
V(T)}d_{T}(u,v)$.

We then consider Column $\ell$. By the definition of $n_{\ell}(T)$, there are
$n_{\ell}(T)$ rows whose entries are equal to $\ell$ while the entries of the
other rows are all $0$. Hence, the summation of all entries of Column $\ell$
is equal to $\ell n_{\ell}(T)$ implying that the summation of all etries in
this matrix is $\sum^{diam(T)}_{\ell=1}\ell n_{\ell}(T)$.

By the counting two way principle, we have that

$\sum_{\\{u,v\\}\subseteq V(T)}d_{T}(u,v)=\sum^{diam(T)}_{\ell=1}\ell
n_{\ell}(T).$

This proves Theorem 2.

## References

  * [1] S. A. U. H. Bokhary and H. Tabassum, The energy of some tree dendrimers, Journal of Applied Mathematics and Computing, 2021.
  * [2] S. A. U. H. Bokhary, M. Imran, and S. Manzoor, On molecular topological properties of dendrimers, Canadian Journal of Chemistry, 94(2)(2015), 120-–125.
  * [3] S. A. U. H. Bokhary, et al. ”On Topological Indices and QSPR Analysis of Drugs Used for the Treatment of Breast Cancer.” Polycyclic Aromatic Compounds (2021): 1-21.
  * [4] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood, 1990.
  * [5] E. W. Buhleier, Vogtle, F. and W. Wehner, Cascade and nonskid-chain-like syntheses of molecular cavity topologies, Synthesis 2 (1978): 155-158.
  * [6] Z. Chen, M. Dehmer, F. Emmert-Streib and Y. Shi, Entropy bounds for dendrimers, Applied Mathematics and Computation, 242(2014), 462–472.
  * [7] F. R. K. Chung, The average distance and the independence number, Journal of Graph Theory, 12(2)(1988), 229–235.
  * [8] P. Dankelmann, S. Mukwembi and H. C. Swart, Average distance and vertex connectivity, Journal of Graph Theory, 62(2)(2009), 157–177.
  * [9] A. A.Dobrynin, R. Entringer and I. Gutman. ”Wiener index of trees: theory and applications.” Acta Applicandae Mathematica 66.3 (2001): 211-249.
  * [10] R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czechoslovak Mathematical Journal, 26(1976), 283–296.
  * [11] S. Fajlowics and W. Waller, On two conjectures of Graffiti, Congressus Numerantium, 55(1986), 51–56.
  * [12] H. Hosoya, Topological Index. A Newly proposed quantity characterizing the topological nature of structural isomers of saturated Hydrocarbons, Bulletin of the Chemical Society of Japan, 1971(44), 2332–2339.
  * [13] M. Jurkiewicz, Average distance is submultiplicative and subadditive with respect to the strong product of graphs, Applied Mathematics and Computation, 315(2017), 278–285.
  * [14] M. Knor, R. Škrekovski and A. Tepeh, Digraphs with large maximum Weiner index, Applied Mathematics and Computation, 284(2016), 260–267.
  * [15] G. Liu and G. Liu, Weiner polarity index of dendrimers, Applied Mathematics and Computation, 322(2018), 151–153.
  * [16] B. Mohar, B. Darko and T. Nenad, A novel definition of the Wiener index for trees, Journal of chemical information and computer sciences 33(1)(1993), 153–154.
  * [17] K. G. Mirajkar and A. Morajkar, On medium domination number of few poly silicates, Malaya Journal of Matematik, 2020, 97–103.
  * [18] G. Mahadevan, V. Vijayalakshmi and C. Sivagnanam, Investigation of the medium domination number of some special types of graphs, Australian Journal of Basic and Applied Sciences, 9(35)(2015), 126–129.
  * [19] G. Mahadevan, V. Vijayalakshmi and C. Sivagnanam, Extended medium domination number of a graph, International Journal of Applied Engineering Research, 10(92)(2015), 355–360.
  * [20] G. Mahadevan and S. Anuthiya, Double twin domination number and its various derived graphs – preprint.
  * [21] G. Mahadevan, S. Avadayappan, V. Vijayalakshmi and A. Akila, Exact values of the medium domination number of some specialized types of graphs, International Journal of Applied Engineering Research, 11(1)(2016), 194–203.
  * [22] D. E. Needham, C. Wei and P. G. Seybold, Molecular modeling of the physical properties of the Alkanes, Journal of American Chemical Society 110(1988), 4186–4194.
  * [23] J. Plesnik, On the sum of all distances in a graph or digraph, Journal of Graph Theory, 8(1984), 1–21.
  * [24] M. Ramachandran and N. Parvathi, The medium domination number of Jahangir graph, Indian Journal of Science Technology, 8(5)(2015): 400–406.
  * [25] D. H. Rouvray, Predicting chemistry from topology, Scientific American, 254(1986), 40–47.
  * [26] M. K. Siddiqui, M. Imran and A. Ahmad, On Zagreb indices, Zagreb polynomials of some nanostar dendrimers, Applied Mathematics and Computation, 280(2016), 132–139.
  * [27] F. Tian and J. M. Xu, Average distances and distance domination numbers, Discrete Applied Mathematics, 157(5)(2009), 1113–1127.
  * [28] D. Vargör, P.Dündar, The medium domination number of a graph, International Journal of Pure and Applied Mathematics, 70(3)(2011), 297–306.
  * [29] H. Wiener, Structural determination of paraffin boiling points. Journal of American Chemical Society, 69(1947), 17–20.


# SceNDD: A Scenario-based Naturalistic Driving Dataset

Avinash Prabu, Nitya Ranjan, Lingxi Li*, Renran Tian, Stanley Chien, Yaobin
Chen, and Rini Sherony This work was supported in part by the Toyota
Collaborative Safety Research Center (CSRC).A. Prabu, N. Ranjan, L. Li, S.
Chien, and Y. Chen are with the Transportation and Autonomous Systems
Institute (TASI), also with the Department of Electrical and Computer
Engineering, Indiana University-Purdue University Indianapolis. Emails:
{aprabu, niranjan, ll7, schien<EMAIL_ADDRESS>Tian is with the
Transportation and Autonomous Systems Institute (TASI), also with the
Department of Computer Information and Graphics Technology, Indiana
University-Purdue University Indianapolis. Email<EMAIL_ADDRESS>Sherony
is with the Collaborative Safety Research Center (CSRC), Toyota Motor North
America, Ann Arbor, MI, USA. Email<EMAIL_ADDRESS>author.

###### Abstract

In this paper, we propose SceNDD: a scenario-based naturalistic driving
dataset that is built upon data collected from an instrumented vehicle in
downtown Indianapolis. The data collection was completed in 68 driving
sessions with different drivers, where each session lasted about 20–40
minutes. The main goal of creating this dataset is to provide the research
community with real driving scenarios that have diverse trajectories and
driving behaviors. The dataset contains ego-vehicle’s waypoints, velocity, yaw
angle, as well as non-ego actor’s waypoints, velocity, yaw angle, entry-time,
and exit-time. Certain flexibility is provided to users so that actors,
sensors, lanes, roads, and obstacles can be added to the existing scenarios.
We used a Joint Probabilistic Data Association (JPDA) tracker to detect non-
ego vehicles on the road. We present some preliminary results of the proposed
dataset and a few applications associated with it. The complete dataset is
expected to be released by early 2023.

##  I INTRODUCTION

The development of connected and automated vehicles (CAVs) technology has been
growing at a fast pace in the last decade [1], [2]. Motion planning is one of
the most important aspects for CAVs. Thus, there is an urgent need for
developing efficient algorithms as well as their verification and validation
methods using benchmark datasets. High-quality datasets enable researchers to
virtually access, visualize, simulate, and analyze real-life urban driving
scenarios, which greatly save their time and energy. In this paper, we develop
SceNDD: a scenario-based naturalistic driving dataset that is built upon data
collected from an instrumented vehicle in downtown Indianapolis. The data
collection was completed in 68 driving sessions with different drivers, where
each session lasts 20–40 minutes. The main goal of creating this dataset is to
provide the research community with real driving scenarios that have diverse
driving trajectories and behaviors to develop efficient motion planning and
path following algorithms.

A multi-model dataset typically needs a combination of sensors for capturing
data. Cameras are used for recording images/videos and the features of
interest can be extracted and analyzed using image processing or computer
vision algorithms. LiDAR data are used for 3D localization. Inertial
measurement unit (IMU) and GPS devices are also popular to get accurate
position, trajectory, velocity, and acceleration of the ego-vehicle. In
literature, datasets such as Waymo Open Dataset[3], nuScenes[4], LYFT[5],
KITTI[6], Argoverse[7], and ApolloScape [8] have been created using a
combination of sensors mentioned above. They are popular benchmark datasets
for the research community to use and develop efficient and effective
algorithms for CAVs.

The nuScenes[4] dataset is one of the most commonly used benchmark datasets
for CAVs. It includes around 6 hours of driving data captured by front-facing
stereo cameras, LiDAR, and GPS/IMU sensors. The LYFT [5] and KITTI [6]
datasets are similar, with difference in the perception environments and data
sizes. These datasets are excellent for developing perception algorithms.
However, they do not focus on capturing motion features such as driving
scenarios and driving behavior.

Recently, multiple motion datasets have been proposed, which include various
driving scenes, tracked objects, moving trajectories, and time segments. A
notable dataset is the Waymo Open dataset [3], which includes motion
prediction, interaction prediction, and occupancy/flow prediction. It is
composed of 574 hours of naturalistic driving data, collected in different
major cities in the U.S. Argoverse[7] is also a dataset that focuses on
certain driving behaviors, such as turning at an intersection and changing
lanes. The Interaction dataset[9] is collected via drone footage and contains
naturalistic motion of various traffic agents in multiple driving scenarios in
various countries, which has diverse and complex behaviors of vehicles at
intersections and roundabouts. However, this dataset does not have 3D state
estimates that our dataset includes. The ApolloScape dataset[8] also includes
trajectories of different traffic agents but does not have trajectory of the
ego vehicle. Datasets such as the Stanford Drone Dataset[10], NGSIM[11],
ETH[12], UCY[13], Town Center[14] are popular in motion forecasting but do not
focus on the driving environment and are much smaller in size compared to our
dataset.

TABLE I: Comparison of various autonomous driving datasets Name | Task | Focus | Environment
---|---|---|---
nuscenes | Perception, Prediction | Varied | Urban Streets
Waymo Open Dataset | Perception, Prediction | Varied | Varied
LYFT | Perception, Planning | Varied | Varied
KITTI | Perception | Pedestrians | Sidewalk
Argoverse Forecasting | Prediction | Varied | Urban Streets
AppolloScape Trajectory | Prediction | Varied | Urban Streets
The Interaction Dataset | Prediction | Vehicles | Ramps, Roundabouts, Intersections
Stanford Drone Dataset | Perception | Pedestrians | Pedestrian only streets, Pedestrian Crossing
NGSIM | Prediction | Pedestrians | Highway
ETH | Prediction | Pedestrians | Pedestrian Crossing, Sidewalk
UCY | Prediction | Pedestrians | Pedestrian Crossing, Sidewalk
Town Center | Prediction | Pedestrians | Sidewalk, Pedestrian only Streets
SceNDD | Prediction, Planning, Flexibility | Vehicles | Varied

Our dataset includes naturalistic driving data of 68 driving sessions with
different drivers, where each session lasts 20–40 minutes. One unique feature
is that it provides flexibility for users to add/remove targets in the
simulated environment and customize the environment to their needs. The
development is based on the Matlab, which allows the addition of different
sensors (e.g., radar, LiDAR, ultrasonic sensors, etc.) to the ego vehicle, so
that it is adaptive to different configurations of the ego-vehicle. Another
attribute of our dataset is the time horizon of prediction. Since all the data
is broken down into scenarios, the data can be easily broken down into
timestamps of different history and horizon time. The comparison of various
autonomous driving dataset is shown in Table I.

To the best of our knowledge, only a few existing datasets provide scenarios
with flexibility in diverse real-time driving. In this paper, we propose
creating a dataset that involves a diverse mix of driving data collected using
different drivers around downtown Indianapolis. The main contributions of this
paper are summarized as follows:

  * •

Create a comprehensive dataset that has 68 driving sessions around downtown
Indianapolis, with each session being 20-40 minutes.

  * •

Process and fuse data from different sensors. In this paper, since only GPS
and the LiDAR data are used for processing, a simple time synchronization of
the sensors is sufficient. In the future versions of the dataset, a camera-
LiDAR sensor fusion will be adopted.

  * •

Develop a pipeline to generate driving scenarios from recorded vehicle data.

##  II Data Acquisition System

In this section, we briefly describe the development of vehicle-based data
acquisition system (DAS), which includes six cameras to cover all 360-degree
angles, one 64-beam 360-degree Ouster LiDAR, a Reach Emlid GPS, and a desktop
computer. The instrumented vehicle is shown in Fig. 1.

Figure 1: The instrumented vehicle for data collection.

###  II-A Cameras

The main features considered while selecting a camera were resolution, frames
per second (FPS), shutter type, connector type, color coding, external
hardware synchronization, data transfer speed, compatibility with ROS
operating system, and cost. FLIR Grasshopper-3 cameras are selected, which are
capable of providing a resolution of $2048\times 2048$, 1 to 90 FPS, and
programmable exposure and shutter speed. The camera also has a global shutter,
which reduces blur due to fast motion. The camera has a CMOS sensor to
facilitate noise reduction and has a GPIO port capable of bi-directional
synchronization with the other sensors. We used two types of lenses, 95∘ and
43∘. The wider-angle lens was used to cover the sides of the vehicle, and the
narrower-angle lens was used to cover the front and back. The camera used is
shown in Fig. 2.

Figure 2: FLIR Grasshopper-3 camera.

###  II-B LiDAR

The Ouster OS-1 64-beam medium-range LiDAR was used in our data collection.
The OS-1 can generate 1,310,720 points at a frequency of 10 Hz, has a
horizontal field of 360 degrees, and a 45 degrees vertical field of view. The
LiDAR has a maximum distance range of 120m with an accuracy of +/- 5cm for
Lambertian targets. OS-1 LiDAR also comes with a sensor interface that allows
for transmitting data over Ethernet using UDP. The sensor interface also has a
multi-purpose I/O port, which can be programmed to synchronize signals with
cameras. The LiDAR is shown in Fig. 3.

Figure 3: Ouster OS-1 64-beam LiDAR.

###  II-C GPS

The Real-time kinematic (RTK) GPS module with base correction is utilized to
detect and track the instrumented vehicle’s position and motion profile. The
system has three key components: 1) Emlid Reach M+ RTK GNSS Module as a rover,
2) Tallysman Global Navigation Satellite System (GNSS) Antenna, and 3) INDOT-
INCORS, a network of GNSS base collection systems operated by the Indiana
Department of Transportation. The base station receives a signal from GPS
satellites, creates a correction factor, and then sends the correction signal
via WI-FI to the rover. Our system uses a 4G hotspot as the WI-FI for the
communication to the base station. The Reach M+ RTK GNSS Module has a 5GB
internal storage and can provide precise navigation and mapping. The GPS
module is shown in Fig. 4.

Figure 4: Reach Emlid M+ RTK GPS.

###  II-D PC

The computer we use runs on Linux 4.15.0-123-generic (x86-64) kernel and is
installed with Ubuntu 20.04 LTS operating system. The system hosts an 8GB
solid-state drive memory. The processor used is an Intel® Xeon(R) W-2123 CPU @
3.60GHz × 8. The system also contains AMD Radeon Pro WX2100 (POLARIS12/DRM
3.23.0 / 4.15.0-123-generic, LLVM 6.0.0) for graphics Open GL rendering. In
addition, the system consists of two SSDs and one hard disk of 500GB each for
data saving. The system uses ROS [15] Noetic for recording data from the
sensors.

###  II-E Sensor Placement

The main goal of the vehicle-based data acquisitions system is to cover 360
degrees around the vehicle and record accurate GPS information. Four cameras
are placed at the corners on the top of the vehicle, and two cameras are
placed at the center, one front-facing and one back facing. The cameras on
corners are equipped with wide-angle lenses, and the cameras at the center are
equipped with 40-degree lenses. The LiDAR is placed at the center of the
vehicle’s roof to provide maximum coverage around the vehicle. The GPS is put
at the back of the vehicle and on the roof. Fig. 5 illustrates the placement
of sensors on the instrumented vehicle.

Figure 5: Sensor placement of the instrumented vehicle.

##  III Overview of the Dataset

The dataset is developed predominantly using the data from GPS and LiDAR, with
the camera images as a reference. Each scenario is sixty seconds in length and
consists of information about the ego vehicle (waypoints, velocity, and yaw
angle), non-ego actors (waypoints, velocity, yaw angle, entry time, and exit
time), and road information (name, centers, and banking angle). The dataset
provides driving scenarios [16] with a diversity in driving behaviors.

###  III-A GPS Processing

The GPS data is recorded as bag files, then extracted to obtain latitude,
longitude, elevation, yaw rate, velocity, and timestamp. The map area covered
by the GPS is then downloaded from the OpenStreetMap [17]. The road network is
then created using MATLAB scenario generator along with road attributes. In
this paper, the lane information is not included. It will be incorporated in
the future using high-definition map service. The GPS data is filtered using
Savitzkey - Golay filter [18], [16] and is used to compute the local
trajectory and velocity of the ego vehicle. Fig. 6 shows the example GPS data
collected in a driving scenario.

Figure 6: Example GPS data.

###  III-B LiDAR Processing

####  III-B1 Data Collected

The LiDAR data is recorded as UDP packets for better transfer speed and
lossless recording. The UDP packets are also stored in bag files. These bag
files are then extracted and the UDP packets are converted to MATLAB point-
cloud object with their respective timestamps. The relative time of each
point-cloud frame with respect to the GPS timestamp is obtained. The LiDAR
data is then used to detect and track the non-ego actors. Fig. 7 shows
exemplary point-cloud data recorded from LiDAR.

Figure 7: Example LiDAR data.

####  III-B2 Object Detection

A virtual driving scenario was created with the GPS, IMU, and LiDAR data. The
GPS data was used to show the trajectory and movement of the targets on a
high-definition map. These scenarios allow the simulation and testing of
different motion planning algorithms.

The Non-Ego actors were detected using the Joint Probabilistic Data
Association algorithm[19] implemented on MATLAB. It allows for the detection
of multiple targets. This algorithm enables estimation of states of unknown
and time-varying targets from noisy and uncertain environments, which measures
and calculates the hypothesis pairs for every agent for every track. Each
track measurement hypothesis has a weight, which is calculated by the
normalized sum of the conditional probabilities of the agent track
association[20]. The tracker employs joint probabilistic data association to
assign detection to each track. Multiple detection can contribute to each
track; hence the tracker uses a soft assignment. Tracks are created,
confirmed, corrected, predicted, and deleted by the tracker. In MATLAB,
Detection reports created by _objectDetection_ object are used as inputs to
the tracker[21].

Any new track begins with a tentative state. If a tentative track receives
enough detection, its status is changed to confirmed. The related track is
instantly confirmed if the detection has a known classification. The tracker
considers a track as a physical object once it has been confirmed. The track
is removed if no detection is assigned within a certain amount of updates. The
tracker calculates the state vector and state estimate error covariance matrix
for each track[21]. Each detection has at least one track associated with it.
If the detection cannot be assigned to an existing track, the tracker creates
a new one. If a tracker maintains multiple tracks, the data association
process becomes more complicated because one detection can fall within the
validation gates of multiple tracks. In our case, clustering is used since
there are multiple actors and tracks in one scenario.

The position and velocity of the surrounding vehicles in relation to the ego
vehicle are provided by LiDAR detection. We converted the target vehicle
positions to global coordinates and approximated the orientation angle based
on vehicle motion using Equation (1) below.

$(X_{t},Y_{t})=(X_{ego},Y_{ego})+R(\psi_{ego})\cdot(x_{t},y_{t})^{T},$ (1)

where $R$ is the Rotation Matrix, $(x_{t},y_{t})$ is the position in the ego
vehicle’s coordinate, and $(X_{t},Y_{t})$ is the position in the global
coordinate.

In scenarios where there are multiple non-ego actors close to each other, an
issue arises where the tracks for all vehicles are noisy, and a track for a
vehicle changes from one lane to another. This issue is resolved by reducing
the default track difference length in MATLAB, which allows separate tracks
for the respective non-ego actors. However, when the track difference length
is small, noisy data can be included in the scenario. These noisy tracks are
manually deleted by verifying the non-ego actors with the camera.

Since the Joint Probabilistic Data Association algorithm performs a soft
assignment, it occasionally allows two non-ego actors very close to each other
to be considered as one non-ego actor. This is again fixed by manually
verifying it with the camera and changing the track assignment size so that
each non-ego actor gets its own track.

###  III-C Camera Data

Figure 8: Example Camera data.

Even though the camera data is currently used as reference for the generated
scenarios, it will be used to add much more information to the dataset in the
future. An example camera view from all six cameras is shown in Fig. 8.

##  IV Scenario Development from the Dataset

This section describes several scenario development as examples and with
reference images. Scenario 1 describes a case where the ego vehicle is in
interaction with two other vehicles, one at the back and one on the right side
in the blind-spot range. This is depicted in the camera images in Fig. 9. The
equivalent scenario generated using Matlab is shown in Fig. 10. The ego-
vehicle is depicted and encircled in blue. Comparing the images in Fig. 9(e)
and Fig. 9(f), it can be seen that it matches with the three vehicles in the
generated scenario. It can also be seen that the vehicle captured by the front
center camera, Fig. 9(b), is not generated in the scenario. This is because
the distance between the ego vehicle and the vehicle in front is large. This
issue can be addressed where cameras are also involved in actor detection.

(a) Left Front

(b) Front Center

(c) Right Front

(d) Left Back

(e) Back Center

(f) Right Back

Figure 9: Reference camera frames - Scenario 1.

(a) Bird’s-eye view.

(b) Ego-centric view.

Figure 10:  Generated Scenario 1.

Scenario 2 depicts the situation where the vehicle in front slows down,
changes lane to the left, and turns left. This can be seen in the reference
images in Fig. 11. In Fig. 11, the front camera, right-front camera, and back
camera shows the cars in view of the ego vehicle. It can also be seen in the
generated scenario, as illustrated in Fig. 12.

(a) Left Front

(b) Front Center

(c) Right Front

(d) Left Back

(e) Back Center

(f) Right Back

Figure 11: Reference camera frames - Scenario 2.

(a) Bird’s-eye view.

(b) Ego-centric view.

Figure 12:  Generated Scenario 2.

(a) Left Front

(b) Front Center

(c) Right Front

(d) Left Back

(e) Back Center

(f) Right Back

Figure 13: Reference camera frames - Scenario 3.

Scenario 3 demonstrates an interaction at a traffic light. The scenario
involves a non-ego vehicle which is about to start after a green light. The
non-ego vehicle is about to be passed on the left by the ego vehicle and
another non-ego vehicle on the right. The camera view is depicted in Fig. 13.
The generated scenario is not shown due to the page limitation.

Note that all scenarios are generated at a frequency of 10 Hz. The scenarios
contain information about all ego and non-ego vehicles’ waypoints, yaw angle,
and the speed at each timestamp (see Fig. 14 as an example). The information
about the scenarios can be exported as a Matlab function to include or change
the scenario variable. We can change the variables of either the ego or non-
ego vehicle to simulate a potential crash scenario. We can also add a barrier
or a guardrail or even another non-ego actor into the scenario to mimic the
real driving situation.

Figure 14: Waypoints of vehicles in a generated scenario.

##  V CONCLUSION

In this paper, we developed a scenario-based dataset using naturalistic
driving data collected around downtown Indianapolis. The dataset contains ego-
vehicle waypoints, velocity, yaw angle, as well as non-ego actors’ waypoints,
velocity, yaw angle, entry-time, and exit-time. The real driving scenarios can
be generated using the driving scenario designer in Matlab. Certain
flexibility is provided to users so that actors, sensors, lanes, roads, and
obstacles can be added to the existing scenarios. This dataset can be exported
and it serves as a great resource for the algorithm development on motion
planning and control.

One future research direction is to enhance the existing dataset with camera-
Lidar fused data. It is also interesting to study driving behavior at
different traffic conditions.

## References

  * [1] Y. Chen and L. Li, Advances in Intelligent Vehicles.  Academic Press, 2013.
  * [2] D. Cao, X. Wang, L. Li, C. Lv, X. Na, Y. Xing, X. Li, Y. Li, Y. Chen, and F.-Y. Wang, “Future directions of intelligent vehicles: Potentials, possibilities, and perspectives,” IEEE Transactions on Intelligent Vehicles, vol. 7, no. 1, pp. 7–10, 2022.
  * [3] S. Ettinger, S. Cheng, B. Caine, C. Liu, H. Zhao, S. Pradhan, Y. Chai, B. Sapp, C. R. Qi, Y. Zhou, Z. Yang, A. Chouard, P. Sun, J. Ngiam, V. Vasudevan, A. McCauley, J. Shlens, and D. Anguelov, “Large scale interactive motion forecasting for autonomous driving: The waymo open motion dataset,” in Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 9710–9719, October 2021.
  * [4] H. Caesar, V. Bankiti, A. H. Lang, S. Vora, V. E. Liong, Q. Xu, A. Krishnan, Y. Pan, G. Baldan, and O. Beijbom, “nuscenes: A multimodal dataset for autonomous driving,” in 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11618–11628, 2020.
  * [5] R. Kesten, M. Usman, J. Houston, T. Pandya, K. Nadhamuni, A. Ferreira, M. Yuan, B. Low, A. Jain, P. Ondruska, S. Omari, S. Shah, A. Kulkarni, A. Kazakova, C. Tao, L. Platinsky, W. Jiang, and V. Shet, “Level 5 perception dataset 2020,” 2019.
  * [6] J. Fritsch, T. Kühnl, and A. Geiger, “A new performance measure and evaluation benchmark for road detection algorithms,” in 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), pp. 1693–1700, 2013.
  * [7] M.-F. Chang, J. Lambert, P. Sangkloy, J. Singh, S. Bak, A. Hartnett, D. Wang, P. Carr, S. Lucey, D. Ramanan, and J. Hays, “Argoverse: 3d tracking and forecasting with rich maps,” in 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 8740–8749, 2019.
  * [8] Y. Ma, X. Zhu, S. Zhang, R. Yang, W. Wang, and D. Manocha, “Trafficpredict: Trajectory prediction for heterogeneous traffic-agents,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 6120–6127, 2019\.
  * [9] W. Zhan, L. Sun, D. Wang, H. Shi, A. Clausse, M. Naumann, J. Kümmerle, H. Königshof, C. Stiller, A. de La Fortelle, and M. Tomizuka, “INTERACTION Dataset: An INTERnational, Adversarial and Cooperative moTION Dataset in Interactive Driving Scenarios with Semantic Maps,” arXiv:1910.03088 [cs, eess], Sept. 2019.
  * [10] A. Robicquet, A. Sadeghian, A. Alahi, and S. Savarese, “Learning social etiquette: Human trajectory understanding in crowded scenes,” in Computer Vision – ECCV 2016 (B. Leibe, J. Matas, N. Sebe, and M. Welling, eds.), (Cham), pp. 549–565, Springer International Publishing, 2016.
  * [11] B. Coifman and L. Li, “A critical evaluation of the next generation simulation (ngsim) vehicle trajectory dataset,” Transportation Research Part B: Methodological, vol. 105, pp. 362–377, 11 2017.
  * [12] S. Pellegrini, A. Ess, K. Schindler, and L. van Gool, “You’ll never walk alone: Modeling social behavior for multi-target tracking,” in 2009 IEEE 12th International Conference on Computer Vision, pp. 261–268, 2009.
  * [13] A. Lerner, Y. Chrysanthou, and D. Lischinski, “Crowds by example,” Computer Graphics Forum, vol. 26, no. 3, pp. 655–664, 2007.
  * [14] B. Benfold and I. Reid, “Stable multi-target tracking in real-time surveillance video,” pp. 3457–3464, 2011.
  * [15] Stanford Artificial Intelligence Laboratory et al., Robotic Operating System.
  * [16] S.-W. Park, K. Patil, W. Wilson, M. W. Corless, G. H. Choi, and P. A. Adam, Creating Driving Scenarios from Recorded Vehicle Data for Validating Lane Centering System in Highway Traffic.  2020\.
  * [17] OpenStreetMap contributors, “Planet dump retrieved from https://planet.osm.org ,” 2017.
  * [18] R. W. Schafer, “What is a savitzky-golay filter? [lecture notes],” IEEE Signal Processing Magazine, vol. 28, no. 4, pp. 111–117, 2011.
  * [19] “Sonar tracking of multiple targets using joint probabilistic data association,” IEEE Journal of Ocean Engineering, pp. 173–184, 1983.
  * [20] Y. Bar-Shalom, F. Daum, and J. Huang, “The probabilistic data association filter,” IEEE Control Systems Magazine, vol. 29, no. 6, pp. 82–100, 2009\.
  * [21] MATLAB, trackerJPDA , 2019.


# Avoiding large squares in trees and planar graphs

Daniel Gonçalves, Pascal Ochem, Matthieu Rosenfeld
LIRMM, CNRS
Université de Montpellier
France

###### Abstract

The Thue number $\pi(G)$ of a graph $G$ is the minimum number of colors needed
to color $G$ without creating a square on a path of $G$. For a graph class
$C$, $\pi(C)$ is the supremum of $\pi(G)$ over the graphs $G\in C$. The Thue
number has been investigated for famous minor-closed classes: $\pi(tree)=4$,
$7\leqslant\pi(outerplanar)\leqslant 12$, and $11\leqslant\pi(planar)\leqslant
768$. Following a suggestion of Grytczuk, we consider the generalized
parameters $\pi_{k}(C)$ such that only squares of period at least $k$ must be
avoided. Thus, $\pi(C)=\pi_{1}(C)$. We show that $\pi_{5}(tree)=2$,
$\pi_{2}(tree)=3$, and $\pi_{k}(planar)\geqslant 11$ for every fixed $k$.

##  1 Introduction

A coloring of a graph $G$ is non-repetitive if the sequence induced by the
colors of any path of $G$ is not a square. The Thue number $\pi(G)$ of $G$ is
the minimum number of colors needed in a non-repetitive coloring $G$. Recall
that the period of a square $uu$ is $|u|$.

For a graph class $C$, $\pi(C)$ is the supremum of $\pi(G)$ over the graphs
$G\in C$. Let $tw_{k}$ denote the class of graphs with treewidth at most $k$.

######  Theorem 1.

  * •

$\pi(path)=3$ [12]

  * •

$\pi(tree)=4$ [7]

  * •

$7\leqslant\pi(outerplanar)\leqslant 12$ [2]

  * •

$\pi(tw_{k})\leqslant 4^{k}$ [9]

  * •

$11\leqslant\pi(planar\cap tw_{3})\leqslant\pi(planar)\leqslant 768$ [5, 4]

Other types of coloring, namely proper coloring and star coloring [1], are
defined by forbidding only squares of period 1 and squares of period 1 and 2,
respectively. The corresponding chromatic numbers $\chi$ and $\chi_{s}$ thus
satisfy $\chi(C)\leqslant\chi_{s}(C)\leqslant\pi(C)$ for every graph class
$C$.

This paper investigates another variation of non-repetitive coloring,
suggested by Grytczuk, such that only large enough squares are forbidden. The
parameter $\pi_{k}(G)$ is the minimum number of colors needed to color $G$
such that no squares of period at least $k$ appears in $G$. We similarly
define $\pi_{k}(C)$ for a graph class $C$, so that
$\pi(C)=\pi_{1}(C)\geqslant\pi_{2}(C)\geqslant\pi_{3}(C)\geqslant\cdots$

The case of words, i.e. infinite paths, is already settled

######  Theorem 2.

  * •

$\pi_{k}(path)=3$ for $1\leqslant k\leqslant 2$ [12]

  * •

$\pi_{k}(path)=2$ for $k\geqslant 3$ [6]

We settle the case of trees in Section 2.

######  Theorem 3.

  * •

$\pi_{1}(tree)=4$

  * •

$\pi_{k}(tree)=3$ for $2\leqslant k\leqslant 4$

  * •

$\pi_{k}(tree)=2$ for $k\geqslant 5$

We also obtain a lower bound for planar graphs in Section 3.

######  Theorem 4.

for every fixed $k$, $\pi_{k}(planar\cap tw_{3})\geqslant 11$.

This disproves a conjecture of Grytczuk [8] that $\pi_{k}(planar)=4$ for some
$k$.

##  2 Trees

Colorings of trees have been considered [11] that minimize the critical
exponent of repetitions. To avoid large squares, and for the same reasons as
in [11], we can assume without loss of generality that our colored tree is
rooted and that all the vertices at the same distance to the root have the
same color. So we only need to describe the word $w$ lying on one branch of
the tree. We adopt the counter-intuitive convention that the reading direction
of $w$ goes towards the root. Then every factor $fs$ of $w$ with $|s|=1$
should be such that $fsf^{R}$ (where $f^{R}$ is the reverse of $f$) avoids the
forbidden large squares. Let $w_{3}$ be any infinite
$\left(\tfrac{7}{4}^{+}\right)$-free ternary word.

We obtain $w$ by taking the image of any $\left(\tfrac{7}{4}^{+}\right)$-free
ternary word by the following morphisms.

We use the $12$-uniform morphism $g_{2}$ to prove $\pi_{2}(tree)\leqslant 3$
and the $21$-uniform morphism $g_{5}$ to prove $\pi_{5}(tree)\leqslant 2$:

$\begin{array}[]{c}g_{2}(\texttt{0})=\texttt{011220012201}\\\
g_{2}(\texttt{1})=\texttt{122001120012}\\\
g_{2}(\texttt{2})=\texttt{200112201120}\\\ \end{array}$

$\begin{array}[]{c}g_{5}(\texttt{0})=\texttt{001101110001010110010}\\\
g_{5}(\texttt{1})=\texttt{001101110001001110101}\\\
g_{5}(\texttt{2})=\texttt{001101110001001101010}\\\ \end{array}$

A word $u$ is _$d$ -directed_ if for every factor $f$ of $u$ of length $d$,
the word $f^{R}$ is not a factor of $u$. To prove that a word is $d$-directed,
it suffices to check its factors of length $d$. A word is $(\beta^{+},n)$-free
if it contains no repetition with exponent strictly greater than $\beta$ and
period at least $n$. To prove the $(\beta^{+},n)$-freeness, we use the method
described in [10]. This way, we obtain the following.

  * •

$g_{2}(w_{3})$ is $3$-directed and $\left(\tfrac{19}{10}^{+},2\right)$-free.

  * •

$g_{5}(w_{3})$ is $20$-directed and $\left(\tfrac{83}{42}^{+},5\right)$-free.

Consider $g_{2}(w_{3})$. For contradiction, suppose that $g_{2}(w_{3})$
contains a factor $fs$ with $|s|=1$ such that the word $fsf^{R}$ contains a
square of period $p\geqslant 20$. Since $fsf^{R}$ is a palindrome, we can
assume that the center of the square is on the left of $s$. Since $fs$ is
$\left(\tfrac{19}{10}^{+},2\right)$-free, $fs$ must contain (as a suffix) a
prefix of this square of length at least $p+1$ and at most $\tfrac{19}{10}p$.
So $sf^{R}$ must contain (as a prefix) a suffix $x$ of this square of length
at most $p$ and at least $\tfrac{1}{10}p+1\geqslant 3$. Because of the square,
$x$ appears both in $fs$ and $sf^{R}$. Notice that $(fs)^{R}=sf^{R}$, so that
$fs$ contains both $x$ and $x^{R}$. This is a contradiction since
$|x|\geqslant 3$ and $fs$ is $3$-directed. Finally, an exhaustive computer
check shows that the words $fsf^{R}$ contain no square of period $p$ with
$2\leqslant p\leqslant 19$.

The proof for $g_{5}(w_{3})$ is similar.

##  3 Planar graphs

We start with helpful results.

######  Lemma 5.

$\pi(planar\cap tw_{3})\geqslant\pi(outerplanar)+4$

###### Proof.

Let $H$ be an outerplanar graph such that $\pi(H)=\pi(outerplanar)$. We
construct a planar graph $G$ as follows. We start with a matching
$a_{1}b_{1},a_{2}b_{2},\cdots,a_{1000}b_{1000}$. For every vertex $x$ in this
matching, we add a copy $H_{x}$ of $H$ and we make $x$ adjacent to every
vertex of $H_{x}$. Finally we add two adjacent vertices $c$ and $d$ and we
make them adjacent to every vertex in the matching.

For contradiction, suppose that $\pi(G)\leqslant\pi(H)+3$ and let $m$ be a
nonrepetitive coloring of $G$ using the alphabet
$A=\left\\{1,2,\cdots,\pi(H)+3\right\\}$. Since $\pi(H)+3\leqslant 15$, two
edges of the matching get the same colors. Without loss of generality,
$m(a_{1})=m(a_{2})=1$ and $m(b_{1})=m(b_{2})=2$. We can also assume that
$m(c)=3$ and $m(d)=4$. Let $u$ be a vertex in $H_{a_{1}}$. Because of the edge
$ua_{i}$, $m(u)\neq 1$. Also $m(u)\neq 3$, since otherwise the path
$ua_{1}ca_{2}$ would create the square $3131$. Symmetrically, $m(u)\neq 4$.
Thus $m(H_{a_{1}})\subset A\setminus\left\\{1,3,4\right\\}$. Since
$|A\setminus\left\\{1,3,4\right\\}|=\pi(H)$, there exists a vertex $u$ in
$H_{a_{1}}$ such that $m(u)=2$. By swapping the roles of colors $1$ and $2$ in
the argument above, we deduce that there exists a vertex $v$ in $H_{b_{1}}$
such that $m(u)=1$. Now the path $ua_{1}b_{1}v$ creates the square $2121$,
which is a contradiction. ∎

######  Lemma 6.

Let $k$ be a fixed integer and let $P$ be a path. In every proper coloring of
$P$ avoiding squares of period at least $k$, every subpath of $P$ with $4k$
vertices contains at least $3$ colors.

###### Proof.

A proper 2-coloring of the path of $4k$ vertices contains the square
$(01)^{2k}$ of period $2k$. So at least $3$ colors are needed to avoid squares
of period at least $k$. ∎

######  Lemma 7.

For every fixed $k$, there exists an outerplanar graph that admits no proper
5-coloring avoiding squares of period at least $k$.

###### Proof.

Our outerplanar graph $G$ has a root vertex and vertices at distance $i$ from
the root are said to be on level $i$. A vertex on level $i+1$ has exactly one
neighbor on level $i$. The neighborhood on level $i+1$ of vertex on level $i$
induces a very long path. Finally, $G$ contains $10k$ levels.

For contradiction, suppose that $G$ has a proper 5-coloring avoiding squares
of period at least $k$ using the colors $\left\\{0,1,2,3,4\right\\}$. Without
loss of generality, the root (on level $0$) is colored $0$. Without loss of
generality, the very long path on level 1 contains two non-intersecting
occurrences of a long factor of the form $w1$. Now we consider the very long
path on level 2 adjacent to the suffix letter $1$ of the rightmost occurrence
of $w1$. It does not contain color $0$, since otherwise we would have the long
square $w10w10$ such that the first $0$ is the root and the second $0$ is on
level 2. So it must be colored with the remaining colors
$\left\\{2,3,4\right\\}$. By Lemma 6, each of the three colors in
$\left\\{2,3,4\right\\}$ are recurrent in our very long path. In particular,
it contains two non-intersecting occurrences of a long factor of the form
$z2$. On level 3, below the suffix letter $2$ of the rightmost occurrence of
$z2$, the very long path does not contain color $2$, since otherwise we would
have the long square $z21z21$. So this very long path on level $3$ must be
colored with letters $\left\\{0,3,4\right\\}$.

Continuing this line of reasonning leads to the existence of a downward path
from the root such that the vertex on level $i$ is colored $i\pmod{5}$. So $G$
contains the long square $(01234)^{2k}$. ∎

We define the sequence $G_{i}$ of planar triangulations with treewidth $3$
such that $G_{0}$ is $K_{4}$ and $G_{i+1}$ is obtained by adding a vertex of
degree $3$ in every face of $G_{i}$.

let us give some properties of the sequence of $G_{i}$.

######  Lemma 8.

If $xy$ is an edge of $G_{i}$, then $x$ and $y$ are adjacent to every vertex
of a path on $t$ vertices in $G_{i+t}$. Moreover, $G_{i}$ and this path have
an empty intersection.

We define the sequence $U_{i}$ of outerplanar graphs as follows:

  * •

every graph $U_{i}$ has exactly one main edge.

  * •

$U_{0}$ is $K_{2}$.

  * •

$U_{i+1}$ is obtained from a copy of $U_{i}$ with main edge $ab$ and a copy of
$U_{i}$ with main edge $cd$ by identifying the vertices $b$ and $c$ and adding
the edge $ad$. Then $ad$ is the main edge of $U_{i+1}$.

It is not hard to check that every outerplanar graph is the subgraph of some
graph $U_{i}$.

######  Lemma 9.

If $x$ is a vertex of $G_{i}$, then $x$ is adjacent to every vertex of a copy
of $U_{t}$ in $G_{i+t+2}$. Moreover, $G_{i}$ and this copy of $U_{t}$ have an
empty intersection.

We are ready to prove Theorem 4. For contradiction, suppose that $q$ is the
smallest integer such that all the $G_{i}$’s can be colored with $10$ colors
such that the period of every square is at most $q$. By Lemma 8, we can assume
that the $10$-coloring is proper and we use the alphabet
$A_{10}=\left\\{0,\cdots,9\right\\}$.

Recall the $\pi(outerplanar)\geqslant 7$ [2]. Using Lemma 5, we obtain
$\pi(planar\cap tw_{3})\geqslant 11$. Let $W$ be a witness of this lower
bound. Then every proper $10$-coloring of a graph $G_{i}$ that contains $W$
must contain a square with period at least 2. This shows that $q\geqslant 2$.

By definiton of $q$, there exists $j$ such that every proper $10$-coloring of
$G_{j}$ contains a square of period $q$. By permuting the colors, we can
assume that this square is $S=0\cdots 10\cdots 1$ where $|0\cdots 1|=q$. By
Lemma 8 and Lemma 6, there exists $a$ such that in $G_{j+a}$, the endpoints of
the edge colored $10$ at the center of $S$ are adjacent to a path containing
$3$ different colors. These $3$ colors are distinct from $0$ and $1$. So
without loss of generality, $G_{j+a}$ contains the three words of the form
$F_{x}=0\cdots 1x0\cdots 1$ with $x\in\left\\{2,3,4\right\\}$.

By Lemma 9 and Lemma 7, there exists $b$ such that in $G_{j+a+b}$, the vertex
colored $1$ that is the common suffix of the words $F_{x}$ is adjacent to an
outerplanar containing $6$ different colors. Let $Q_{6}\subset A_{10}$ be the
set of these $6$ colors. First, $1\not\in Q_{6}$ because the coloring is
proper. If there exists $x\in Q_{6}\cap\left\\{2,3,4\right\\}$, then
$G_{j+a+b}$ would contain the square $F_{x}x=0\cdots 1x0\cdots 1x$ with period
$q+1$. That would contradict the minimality of $q$, so
$Q_{6}\cap\left\\{2,3,4\right\\}=\emptyset$. Therefore,
$Q_{6}=\left\\{0,5,6,7,8,9\right\\}$. Since $0\in Q_{6}$, $G_{j+a+b}$ contains
the overlap $0\cdots 10\cdots 10$.

We have seen that the square with period $q$ and length $2q$ in $G_{j+a}$
extends to one letter to right in $G_{j+a+b}$ to give the overlap with period
$q$ and length $2q+1$. Similarly, the suffix of length $2q$ of this overlap in
$G_{j+a+b}$ is again a square that extends to an overlap in $G_{j+2(a+b)}$. So
$G_{j+2(a+b)}$ contains a repetition with period $q$ and length $2q+2$. By
induction, $G_{j+2q(a+b)}$ contains a repetition with period $q$ and length
$4q$. This repetition in $G_{j+2q(a+b)}$ is a fourth power with period $q$ and
thus a square with period $2q$. Finally, this contradicts the minimality of
$q$.

## References

  * [1] M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kündgen, and R. Ramamurthi. Coloring with no 2-Colored $P_{4}$’s. _The Electronic Journal of Combinatorics_ 11(1):#R26, 2004.
  * [2] J. Barát and P. P. Varjú. On square-free vertex colorings of graphs. _Studia Sci. Math. Hungar._ , 44(3):411–422, 2007.
  * [3] J. Barát and P. P. Varjú. On square-free edge colorings of graphs. _Ars Combin._ , 87:377–383, 2008.
  * [4] V. Dujmovic, L. Esperet, G. Joret, B. Walczak, and D. R. Wood. Planar graphs have bounded nonrepetitive chromatic number. _Advances in combinatorics_ 5 (2020), 73–80.
  * [5] V. Dujmovic, F. Frati, G. Joret, D.R. Wood. Nonrepetitive colourings of planar graphs with $O(\log n)$ colours, _The Electronic Journal of Combinatorics_ 20(R1), 1–11 (2013)
  * [6] R. C. Entringer, D. E. Jackson, and J. A. Schatz.  On nonrepetitive sequences.  J. Combin. Theory. Ser. A 16 (1974), 159–164.
  * [7] J. Grytczuk. Nonrepetitive colorings of graphs - a survey, _Int. J. Math. Math. Sci._ (2007), Art. ID 74639, 10 pp.
  * [8] J. Grytczuk.
http://www.i2m.univ-amu.fr/wiki/Combinatorics-on-Words-
seminar/_media/seminar2020:slides20201005grytczuk.pdf

  * [9] A. Kündgen and M. J. Pelsmajer. Nonrepetitive colorings of graphs of bounded tree-width. _Discrete Math._ , 308(19):4473–4478, 2008.
  * [10] P. Ochem. A generator of morphisms for infinite words. _RAIRO - Theoret. Informatics Appl._ , 40:427–441, 2006.
  * [11] P. Ochem and E. Vaslet. Repetition thresholds for subdivided graphs and trees. _RAIRO - Theoretical Informatics and Applications_ , 46(1):123–130, 2012.
  * [12] A. Thue. Über unendliche Zeichenreihen. _Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania_ , 7 (1906), 1–22.