Starlike tree

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]

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}}}$

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]

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]

• Weisstein, Eric W. "Spider Graph". MathWorld.
• (sequence A004250 in the OEIS)