Starlike tree

Short description: Tree graph with exactly one vertex of degree >2

A starlike tree

In the mathematical subdiscipline of 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 can be seen as resulting from attaching to this central vertex at least three linear graphs (paths). Starlike trees are also referred to as spider graphs.

Definition

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

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. The graph Laplacian has always only one eigenvalue equal or greater than 4.

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 $\mathrm{\Delta }$. For starlike trees $S(n_1,\dots ,n_k)$ with $k\ge 4$ and $n_1,\dots ,n_k\ge 2$, the spectral radius ${\lambda }_1$ satisfies:

$\frac{k-1}{\sqrt{k-2}}<{\lambda }_1(S(n_1,\dots ,n_k))<\frac{k}{\sqrt{k-1}}$

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

$\frac{\mathrm{\Delta }-1}{\sqrt{\mathrm{\Delta }-2}}<{\lambda }_1<\frac{\mathrm{\Delta }}{\sqrt{\mathrm{\Delta }-1}}$

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

For specific cases:

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

Eigenvalues in the interval (−2, 2)

The eigenvalues of starlike trees have been characterized with respect to the interval $(-2,2)$. A starlike tree $S(n_1,n_2,n_3)$ with three branches has all of its eigenvalues in the open interval $(-2,2)$ if and only if it is isomorphic to one of the following:

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

For starlike trees with four or more branches $(k\ge 4)$, at least one eigenvalue lies outside the interval $(-2,2)$.

Topological indices

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

For a starlike tree $X$ with $n$ vertices and central degree $k$, any such index satisfies $TI(X)=k_1{P}_k+k{Q}_k+(n-1){\phi }_{22}$, where $k_1$ is the number of branches of length 1, $P_k={\phi }_{1k}+{\phi }_{22}-{\phi }_{12}-{\phi }_{2k}$, and $Q_k={\phi }_{12}+{\phi }_{2k}-2{\phi }_{22}$. This shows that the index value depends primarily on the number of unit-length branches.

Among all starlike trees on $n$ vertices, the extremal values are typically attained by the star graph $S(1,1,\dots ,1)$ with $n-1$ branches and the tree $S(2,2,n-5)$. For indices where $P_k\le 0$ for all $k\ge 3$ (including the Randić, harmonic, sum-connectivity, geometric-arithmetic, and augmented Zagreb indices), the star graph attains the minimum and $S(2,2,n-5)$ attains the maximum. The reverse holds for indices where $P_k\ge 0$ (including the first Zagreb, Albertson, and atom-bond connectivity indices).

External links

• Weisstein, Eric W.. "Spider Graph". http://mathworld.wolfram.com/SpiderGraph.html. 
• (sequence A004250 in the OEIS)