Closed-Form Analysis and Extremal Bounds of Albertson and Sigma Indices in Trees with Prescribed Degree Sequences

2025

Read Closed-Form Analysis and Extremal Bounds of Albertson and Sigma Indices in Trees with Prescribed Degree Sequences (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19490.txt.

Introduction

Jasem Hamoud and three co-authors study how irregular two families of trees can be, using measures from chemical graph theory. Trees here are branching networks, and caterpillar trees, where vertices hang off a central spine, often model molecular chains. The team works with trees whose degree sequences, the lists of connections per vertex, are fixed in advance.

They derive a closed-form expression for the Albertson index of caterpillar trees and set extreme-value bounds for both the Albertson and sigma indices across the tree families considered. Together the results give one framework for comparing the linear and quadratic irregularity measures. The findings add structural insight for chemical graph theory and extremal graph analysis.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19490

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Closed-Form Analysis and Extremal Bounds of Albertson and Sigma Indices in Trees with Prescribed Degree Sequences Abstract This study explores the irregularity properties of trees with prescribed degree sequences by analyzing two prominent topological indices: the Albertson index and the sigma index. With a particular emphasis on caterpillar trees—frequently used to model molecular chains—we derive a closed-form expression for the Albertson index: irr ⁡ ( 𝒞 ⁡ ( n , m ) ) = m ⁡ ( m + 1 ) ​ n − 2 ​ m + 2 , for ​ n ≥ 3 . \mathrm{irr}(\mathscr{C}(n,m))=m(m+1)n-2m+2,\quad\text{for }n\geq 3. Furthermore, we establish extremal bounds for both indices across tree families characterized by fixed degree sequences. The results yield a unified analytical framework for comparing linear and quadratic irregularity measures, and provide new structural insights relevant to applications in chemical graph theory and extremal graph analysis. Jasem Hamoud 1 Alexey Belov Yakovlevich 2 Muaadh Almahalebi 3 Duaa Abdullah 4 1,2,4 Physics and Technology School of Applied Mathematics and Informatics Moscow Institute of Physics and Technology, 141701, Moscow region, Russia 3 Laboratory Analysis, Geometry and Applications, Department of Mathematics, Faculty of Sciences, University of Ibn Tofail, Kenitra, Morocco. Email: 1 [email protected] , 2 [email protected] 3 [email protected] , 4 [email protected] AMS Classification 2010: 05C05, 05C12, 05C20, 05C25, 05C35, 05C76, 68R10. UDC: 519.172.1 Keywords: Albertson index, Sigma index, Graph irregularity, Degree sequence, Caterpillar trees, Extremal graph theory, Topological indices. 1 Introduction The study of structural irregularity in graphs has garnered increasing attention in both theoretical and applied contexts, particularly in mathematical chemistry, network analysis, and algorithmic graph theory. A graph is said to be regular if all of its vertices have equal degrees; otherwise, it exhibits some degree of irregularity. Accurately quantifying this irregularity is essential for modeling complex systems and understanding the behavior of real-world networks. One of the earliest and most influential measures of graph irregularity is the Albertson index , introduced in [ 3 ] , and defined for a simple graph G=(V,E) as: \mathrm{irr}(G)=\sum_{uv\in E(G)}|\deg_{G}(u)-\deg_{G}(v)|, where \deg_{G}(u) denotes the degree of vertex u . This index captures local disparities between adjacent vertex degrees and has inspired numerous variants and generalizations [ 2 , 1 ] . Parallel foundational contributions by Harary [ 17 ] and Chen [ 6 ] provided combinatorial frameworks that laid the groundwork for modern graph descriptors. To further enrich the understanding of irregularity, global measures such as the total irregularity \mathrm{irr}_{T}(G) have been proposed [ 1 ] , satisfying inequalities that relate them to local measures (e.g., \mathrm{irr}_{T}(G)\leq(n-2)\,\mathrm{irr}(G) for trees [ 11 ] ). More recently, the Sigma index was introduced as a quadratic analogue of the Albertson index [ 15 ] , defined by: \sigma(G)=\sum_{uv\in E(G)}(\deg_{G}(u)-\deg_{G}(v))^{2}=F(G)-2M_{2}(G), where F(G) is the sum of squared degrees over all edges, and M_{2}(G) is the second Zagreb index. This formulation amplifies large degree differences and provides a more sensitive measure of irregularity. Beyond general graphs, a growing body of literature has focused on trees with constrained degree sequences. Studies by Molloy and Reed [ 18 ] and Broutin and Marckert [ 5 ] explored their asymptotic behavior, while Zhang et al. [ 21 ] investigated realizability and enumeration under degree constraints. These results have proven instrumental in analyzing extremal irregularity measures in structured tree families. Among such families, caterpillar trees —characterized by a linear backbone with attached pendant vertices—have emerged as key models in chemical graph theory [ 22 ] . Their tractable structure allows the derivation of explicit analytical expressions. While prior work [ 8 , 19 ] has examined irregularity bounds in these trees, closed-form expressions for both the Albertson and Sigma indices remain scarce. This paper addresses this gap by deriving new closed-form formulas for the Albertson and Sigma indices in caterpillar trees with prescribed degree sequences. In addition, we investigate extremal configurations that maximize or minimize these indices, and we establish structural criteria and comparative bounds. Our findings contribute a unified framework for analyzing linear and quadratic irregularity in trees, with implications for discrete mathematics, chemical graph theory, and network modeling. 2 Preliminaries This section presents essential definitions and previously established results that form the theoretical foundation for our analysis of graph irregularity in trees. We introduce the primary irregularity indices studied in the literature, namely the Albertson and Sigma indices, along with related global and spectral measures. These tools are fundamental for understanding the structure and behavior of graphs with prescribed degree sequences, especially caterpillar trees. We begin with the concept of total irregularity, which provides a global measure of degree disparity across all pairs of vertices in a graph. Definition 1 (Total Irregularity [ 1 ] ) . The total irregularity of a graph G is defined by \operatorname{irr}_{T}(G)=\sum_{\{u,v\}\subseteq V(G)}|\deg_{G}(u)-\deg_{G}(v)|. Next, we recall the notion of a degree sequence, which is a basic descriptor of a graph’s structure and plays a central role in our classification of trees. Definition 2 (Degree Sequence [ 10 ] ) . Let G=(V,E) be a simple graph, where V=\{v_{1},v_{2},\ldots,v_{n}\} , let \mathscr{D}(G)=(\deg_{G}(v_{1}),\dots,\deg_{G}(v_{n})) be a degree sequence of G where \deg_{G}(v_{1})\geqslant\deg_{G}(v_{2})\geqslant\dots\geqslant\deg_{G}(v_{n}) . When \mathscr{D}(G)=(k,k,\ldots,k) , then G is regular of degree k . Otherwise, the graph is irregular. The following result, specific to trees, establishes an upper bound on total irregularity in terms of the Albertson index. Proposition 2.1 ( [ 11 ] ) . Let G be a tree with n\geq 3 vertices. Then: \operatorname{irr}_{T}(G)\leq(n-2)\,\operatorname{irr}(G). Several classical indices, such as the Zagreb indices, are also used to quantify structural features of graphs, particularly in chemical graph theory. Definition 3 (Zagreb Indices [ 12 , 13 ] ) . Let G=(V,E) be a graph. The first and second Zagreb indices are given by M_{1}(G)=\sum_{v\in V(G)}\deg_{G}(v)^{2},\quad M_{2}(G)=\sum_{uv\in E(G)}\deg_{G}(u)\deg_{G}(v). The sigma index, introduced as a quadratic analogue of the Albertson index, emphasizes larger degree differences by squaring them. It provides a refined sensitivity to irregularity. Definition 4 ( \sigma -Maximum and Minimum) . Let \mathcal{S} be a class of graphs, then maximum Sigma \sigma_{\max} , minmum Sigma \sigma_{\min} of a graph G , given by: \displaystyle\sigma_{\max}(\mathcal{S})=\max\{\sigma(G)\mid G\in\mathcal{S}\}, \displaystyle\sigma_{\min}(\mathcal{S})=\min\{\sigma(G)\mid G\in\mathcal{S}\}. Definition 5 . Let \delta(G) and \Delta(G) denote the minimum and maximum degrees in graph G , and let \bar{d}(G)=2m/n where n=|V(G)| and m=|E(G)| denote the average degree. We also denote by \mathcal{G}(n) the class of all connected graphs with n vertices. The next proposition gives a lower bound for the Albertson index of a graph in terms of its extremal degrees, offering insight into the effect of degree disparity. Proposition 2.2 ( [ 8 ] ) . Let G be a graph with minimum degree \delta , maximum degree \Delta , and vertex set of size n . Then: \operatorname{irr}(G)>\frac{\delta(\Delta-\delta)^{2}\cdot n}{\Delta+1}. In addition to combinatorial descriptors, spectral parameters of the graph—such as the adjacency matrix’s largest eigenvalue—have been heuristically related to irregularity, as shown below. Proposition 2.3 (Spectral Approximation [ 7 , 4 ] ) . Let \lambda(G) denote the largest eigenvalue (spectral radius) of the adjacency matrix of G , and let \bar{d}(G) be the average degree. Then: \operatorname{irr}(G)\approx\lambda(G)-\bar{d}(G). Remark 1 . This is not a strict equality and holds under special structural assumptions only. The following classical result characterizes the maximum possible irregularity among all connected graphs of

Read the complete text