Starlike tree
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. More formally, let k \geq 3 and n_1, \ldots, n_k \geq 1 be positive integers.
The starlike tree S(n_1, \ldots, 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, \ldots, n_k) is n_1 + \cdots + n_k + 1 .
The simplest starlike tree is the star graph S_k = S(1, \ldots, 1) with k branches of length one. or equivalently, in terms of the maximum degree \Delta = k : \frac{\Delta - 1}{\sqrt{\Delta - 2}} These bounds show that the spectral radius of such starlike trees is asymptotically \sqrt{\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 \geq 4 and all branches have length 1 (i.e., the tree is a star S_{k+1} ), then \lambda_1 = \sqrt{k} Vertex-degree-based topological indices are molecular descriptors defined as TI(G) = \sum_{1 \leq i \leq j \leq n-1} m_{ij}(G) \varphi_{ij} , where m_{ij}(G) is the number of edges between vertices of degree i and degree j , and the values \varphi_{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)\varphi_{22} , where k_1 is the number of branches of length 1, P_k = \varphi_{1k} + \varphi_{22} - \varphi_{12} - \varphi_{2k} , and Q_k = \varphi_{12} + \varphi_{2k} - 2\varphi_{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, \ldots, 1) with n-1 branches and the tree S(2, 2, n-5) . For indices where P_k \leq 0 for all k \geq 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 \geq 0 (including the first Zagreb, Albertson, and atom-bond connectivity indices).
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1349176183 under CC BY-SA 4.0; modifications have been made.