Starlike tree

In the area of mathematics known as graph theory, a tree is said to be starlike if it has exactly one vertex of degree greater than 2. This high-degree vertex is the root (or central vertex) and a starlike tree is obtained by attaching at least three linear graphs to this central vertex. Such a graph is also referred to as a spider graph.

A starlike tree

Definition

More formally, let ${\displaystyle k\geq 3}$ and ${\displaystyle n_{1},\ldots ,n_{k}\geq 1}$ be positive integers. The starlike tree ${\displaystyle S(n_{1},\ldots ,n_{k})}$ is a tree ${\displaystyle T}$ with a central vertex ${\displaystyle v}$ of degree ${\displaystyle k}$ such that ${\displaystyle T\setminus v\cong P_{n_{1}}\cup \cdots \cup P_{n_{k}}}$, where ${\displaystyle P_{t}}$ denotes the path graph on ${\displaystyle t}$ vertices, and every neighbor of ${\displaystyle v}$ in ${\displaystyle T}$ has degree one or two. The total number of vertices in ${\displaystyle S(n_{1},\ldots ,n_{k})}$ is ${\displaystyle n_{1}+\cdots +n_{k}+1}$. The simplest starlike tree is the star graph ${\displaystyle S_{k}=S(1,\ldots ,1)}$ with ${\displaystyle k}$ branches of length one.^[1]

Properties

Spectral properties

Two finite starlike trees are isospectral, i.e. their graph Laplacians have the same spectra, if and only if they are isomorphic.^[2] The graph Laplacian has always only one eigenvalue equal or greater than 4.^[3]

Spectral radius bounds

The spectral radius of a starlike tree (the largest eigenvalue of its adjacency matrix) can be bounded in terms of its maximum degree ${\displaystyle \Delta }$. For starlike trees ${\displaystyle S(n_{1},\ldots ,n_{k})}$ with ${\displaystyle k\geq 4}$ and ${\displaystyle n_{1},\ldots ,n_{k}\geq 2}$, the spectral radius ${\displaystyle \lambda _{1}}$ satisfies:^[1]

${\displaystyle {\frac {k-1}{\sqrt {k-2}}}<\lambda _{1}(S(n_{1},\ldots ,n_{k}))<{\frac {k}{\sqrt {k-1}}}}$

or equivalently, in terms of the maximum degree ${\displaystyle \Delta =k}$:

${\displaystyle {\frac {\Delta -1}{\sqrt {\Delta -2}}}<\lambda _{1}<{\frac {\Delta }{\sqrt {\Delta -1}}}}$

These bounds show that the spectral radius of such starlike trees is asymptotically ${\displaystyle {\sqrt {\Delta }}}$ as the maximum degree grows large.

For specific cases:^[1]

• If ${\displaystyle k=3}$ and all branches have length 1, then ${\displaystyle \lambda _{1}={\sqrt {3}}}$
• If ${\displaystyle k=3}$ and all branches have length 2, then ${\displaystyle \lambda _{1}=2}$
• If ${\displaystyle k\geq 4}$ and all branches have length 1 (i.e., the tree is a star ${\displaystyle S_{k+1}}$), then ${\displaystyle \lambda _{1}={\sqrt {k}}}$

Eigenvalues in the interval (−2, 2)

The eigenvalues of starlike trees have been characterized with respect to the interval ${\displaystyle (-2,2)}$. A starlike tree ${\displaystyle S(n_{1},n_{2},n_{3})}$ with three branches has all of its eigenvalues in the open interval ${\displaystyle (-2,2)}$ if and only if it is isomorphic to one of the following:

• ${\displaystyle S(1,1,m)}$ for any positive integer ${\displaystyle m}$
• ${\displaystyle S(1,2,2)}$, ${\displaystyle S(1,2,3)}$, or ${\displaystyle S(1,2,4)}$

For starlike trees with four or more branches ${\displaystyle (k\geq 4)}$, at least one eigenvalue lies outside the interval ${\displaystyle (-2,2)}$.^[1]

Topological indices

Vertex-degree-based topological indices are molecular descriptors defined as ${\displaystyle TI(G)=\sum _{1\leq i\leq j\leq n-1}m_{ij}(G)\varphi _{ij}}$, where ${\displaystyle m_{ij}(G)}$ is the number of edges between vertices of degree ${\displaystyle i}$ and degree ${\displaystyle j}$, and the values ${\displaystyle \varphi _{ij}}$ determine the specific index. Examples include the Randić index, first Zagreb index, harmonic index, and atom-bond connectivity index.^[4]

For a starlike tree ${\displaystyle X}$ with ${\displaystyle n}$ vertices and central degree ${\displaystyle k}$, any such index satisfies ${\displaystyle TI(X)=k_{1}P_{k}+kQ_{k}+(n-1)\varphi _{22}}$, where ${\displaystyle k_{1}}$ is the number of branches of length 1, ${\displaystyle P_{k}=\varphi _{1k}+\varphi _{22}-\varphi _{12}-\varphi _{2k}}$, and ${\displaystyle Q_{k}=\varphi _{12}+\varphi _{2k}-2\varphi _{22}}$. This shows that the index value depends primarily on the number of unit-length branches.^[4]

Among all starlike trees on ${\displaystyle n}$ vertices, the extremal values are typically attained by the star graph ${\displaystyle S(1,1,\ldots ,1)}$ with ${\displaystyle n-1}$ branches and the tree ${\displaystyle S(2,2,n-5)}$. For indices where ${\displaystyle P_{k}\leq 0}$ for all ${\displaystyle k\geq 3}$ (including the Randić, harmonic, sum-connectivity, geometric-arithmetic, and augmented Zagreb indices), the star graph attains the minimum and ${\displaystyle S(2,2,n-5)}$ attains the maximum. The reverse holds for indices where ${\displaystyle P_{k}\geq 0}$ (including the first Zagreb, Albertson, and atom-bond connectivity indices).^[4]