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 ≥ 3 {\displaystyle k\geq 3} and n 1 , … , n k ≥ 1 {\displaystyle n_{1},\ldots ,n_{k}\geq 1} be positive integers. The starlike tree S ( n 1 , … , n k ) {\displaystyle S(n_{1},\ldots ,n_{k})} is a tree T {\displaystyle T} with a central vertex v {\displaystyle v} of degree k {\displaystyle k} such that T ∖ v ≅ P n 1 ∪ ⋯ ∪ P n k {\displaystyle T\setminus v\cong P_{n_{1}}\cup \cdots \cup P_{n_{k}}} , where P t {\displaystyle P_{t}} denotes the path graph on t {\displaystyle t} vertices, and every neighbor of v {\displaystyle v} in T {\displaystyle T} has degree one or two. The total number of vertices in S ( n 1 , … , n k ) {\displaystyle S(n_{1},\ldots ,n_{k})} is n 1 + ⋯ + n k + 1 {\displaystyle n_{1}+\cdots +n_{k}+1} . The simplest starlike tree is the star graph S k = S ( 1 , … , 1 ) {\displaystyle S_{k}=S(1,\ldots ,1)} with k {\displaystyle 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 Δ {\displaystyle \Delta } . For starlike trees S ( n 1 , … , n k ) {\displaystyle S(n_{1},\ldots ,n_{k})} with k ≥ 4 {\displaystyle k\geq 4} and n 1 , … , n k ≥ 2 {\displaystyle n_{1},\ldots ,n_{k}\geq 2} , the spectral radius λ 1 {\displaystyle \lambda _{1}} satisfies:
k − 1 k − 2 < λ 1 ( S ( n 1 , … , n k ) ) < k k − 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 Δ = k {\displaystyle \Delta =k} :
Δ − 1 Δ − 2 < λ 1 < Δ Δ − 1 {\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:
If k = 3 {\displaystyle k=3} and all branches have length 1, then λ 1 = 3 {\displaystyle \lambda _{1}={\sqrt {3}}}
… excerpt ends here. Continue reading the full article.
