Swathi Shetty
1 · 2025
Read Swathi Shetty by 1 (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-2512-23199.txt.
Introduction
Swathi Shetty, B. R. Rakshith, and Sayinath Udupa settle a batch of open problems about the ABS index. That degree-based graph invariant has become a standard tool in chemical and spectral graph theory. Ali and co-authors had asked which graphs maximize the index inside several natural families, and this paper answers all of their questions completely.
The families are connected graphs with given counts of vertices and cut-vertices. They also include connected graphs whose vertices split into a prescribed number of independent parts. The third family is connected bipartite graphs with fixed vertex connectivity. In each case the extremal graphs are characterized, meaning the exact shapes achieving the maximum ABS index are identified rather than merely bounded. Such characterizations are useful because extremal shapes reveal what structural features the index rewards, guiding both chemical applications and further theory about degree-based invariants.
Catalog record
| CREATOR | 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-23199
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Swathi Shetty 1 Abstract Recently, Ali et al. [ 1 ] posed several open problems concerning extremal graphs with respect to the 𝒜 ℬ 𝒮 \mathcal{ABS} index. These problems involve characterizing graphs that attain the maximum 𝒜 ℬ 𝒮 \mathcal{ABS} index within specific graph classes, including: (i) connected graphs with n n vertices and p p cut-vertices; (ii) connected graphs of order n n with vertex k k -partiteness v k ( G ) = r v_{k}(G)=r ; and (iii) connected bipartite graphs of order n n with a fixed vertex connectivity κ \kappa . In this paper, we provide complete solutions to all of these problems. . On extremal graphs with respect to the \mathcal{ABS} index \text{July 23, 2025}^{\dagger} † † footnotetext: *Corresponding author; \dagger Initial journal submission date AMS Classification: 05C09, 05C35, 05C92. Key Words: \mathcal{ABS} index, vertex connectivity, vertex k -partiteness. 1 Introduction Throughout the paper, G stands for a graph on n vertices without any loops and multiple-edges. As usual, we denote the vertex set and the edge set of G by V(G) and E(G) , respectively. Two adjacent vertices v_{i} and v_{j} are represented as v_{i}\sim v_{j} , or i\sim j . The degree of a vertex v_{i} in G is denoted as d_{G}(v_{i})/d(v_{i}). The vertex connectivity \kappa of G is the cardinality of a minimum vertex cut set. The vertex k -partiteness of G , v_{k}(G) is the minimum number of vertices whose removal results in a k -partite graph. Topological indices, a well-known class of graph invariants, are numerical values derived from the structure of a graph. In molecular graph theory, these indices are widely used as they often reflect the physicochemical properties of the corresponding molecules. For some recent studies on topological indices, see [ 4 , 6 ] . The atom-bond sum connectivity index, commonly known as the \mathcal{ABS} index, is a recently introduced topological invariant that has quickly attracted significant attention. It is defined as \mathcal{ABS}(G)=\sum\limits_{uv\in E(G)}\sqrt{1-\dfrac{2}{d(u)+d(v)}} . The chemical relevance of the \mathcal{ABS} index is explored in [ 2 ] , while its extremal values and bounds are investigated in [ 7 , 8 ] . Recently, in the review paper [ 1 ] , Ali et al. listed known bounds and extremal results related to the \mathcal{ABS} index. They also stated several new extremal results that follow easily from existing general findings. Furthermore, the authors posed several open problems concerning extremal graphs with respect to the \mathcal{ABS} index. These problems involve characterizing graphs that attain the maximum \mathcal{ABS} index within specific graph classes, including: (i) connected graphs with n vertices and p cut-vertices; (ii) connected graphs of order n with vertex k -partiteness v_{k}(G)=r ; and (iii) connected bipartite graphs of order n with a fixed vertex connectivity \kappa . Motivated by these works, in this paper, we provide complete solutions to all of these problems. 2 \mathcal{ABS} index of graphs with the given number of cut-vertices Let \mathbb{V}_{n}^{p} be the collection of all connected graphs of order n with p number of cut-vertices. We need the following theorem to prove our results in this section. Theorem 2.1 . [ 9 , 1 ] If G is a graph attaining the maximum \mathcal{ABS} index in \mathbb{V}_{n}^{p} , then every block of G is a clique and every cut-vertex of G is contained in exactly two blocks. Lemma 2.2 . Let G be a graph that attains the maximum \mathcal{ABS} index in \mathbb{V}_{n}^{p} . Then G is either the path graph P_{n} or it can be formed by attaching one of the end vertices of a path P^{i} (with a length of at least 1) to a vertex u_{i} of the complete graph K_{n-p} (with vertex labels u_{1},u_{2},\ldots,u_{n-p} ) for 1\leq i\leq k , where 1\leq k\leq n-p . Proof. By Theorem 2.1 , every block of G is a clique and every cut-vertex of G is contained in exactly two blocks. Let H_{1}=K_{\alpha} and H_{2}=K_{\beta} be the two largest cliques in G , where \alpha\geq\beta\geq 2 . Assume that \beta\geq 3 . Case 1: Suppose H_{1} and H_{2} share a common cut-vertex, say x of G . Let y be a vertex of minimum degree in H_{2}\backslash\{x\} , and z be a vertex of H_{2} that is different from the vertices x and y . Let G^{\prime} be the graph obtained from G by removing all the edges of H_{2} which are incident with y except the edge xy , and then joining each vertex of H_{2}\backslash\{x,y\} with every vertex in H_{1}\backslash\{x\} . Then d_{G^{\prime}}(u)=d_{G}(u)+\beta-2 for u\in V(H_{1})\backslash\{x\} , and d_{G^{\prime}}(w)=d_{G}(w)+\alpha-2 for w\in V(H_{2})\backslash\{x,y\} . Also, d_{G}(x)=d_{G^{\prime}}(x)=\alpha+\beta-2 . Importantly, the cut-vertices of G and G^{\prime} are essentially the same. We now consider the following subcases. Subcase 1.1: The vertex y is not a cut-vertex of G . Then d_{G}(y)=\beta-1 and d_{G^{\prime}}(y)=1 . Therefore, \mathcal{ABS}(G)-\mathcal{ABS}(G^{\prime})< \displaystyle\sum_{w:w\in V(H_{2})\backslash\{y\}}\sqrt{1-\dfrac{2}{d_{G}(w)+d_{G}(y)}}-\sum_{u:u\in V(H_{1})\backslash\{x\}}\,\,\sum_{w:w\in V(H_{2})\backslash\{x,y\}}\sqrt{1-\dfrac{2}{d_{G^{\prime}}(u)+d_{G^{\prime}}(w)}} . Since d_{G}^{\prime}(u)+d_{G^{\prime}}(w)>d_{G}(u)+d_{G}(y) and |V(H_{1})|\geq 3 , \mathcal{ABS}(G)<\mathcal{ABS}(G^{\prime}) , a contradiction. Subcase 1.2: The vertex y is a cut-vertex of G . Then d_{G}(y)\leq 2\beta-2 and d_{G^{\prime}}(y)\leq\beta . Let u_{1} ( \neq x ) be a vertex in H_{1} . If | V(H_{2})|\geq 4 , then V(H_{2})\backslash\{x,y,z\}\neq\emptyset . Let w_{1} be a vertex in V(H_{2})\backslash\{x,y,z\} . Then \mathcal{ABS}(G)-\mathcal{ABS}(G^{\prime})< \displaystyle\displaystyle\sum_{w:w\in V(H_{2})\backslash\{y\}}\sqrt{1-\dfrac{2}{d_{G}(w)+d_{G}(y)}}-\sum_{w:w\in V(H_{2})\backslash\{x,y\}}\sqrt{1-\dfrac{2}{d_{G^{\prime}}(w)+d_{G^{\prime}}(u_{1})}} \displaystyle+\sum_{\underset{y^{\prime}\notin V(H_{2})}{y^{\prime}:y^{\prime}\sim y}}\sqrt{1-\dfrac{2}{d_{G}(y^{\prime})+d_{G}(y)}}-\sum_{u:u\in V(H_{1})\backslash\{x,u_{1}\}}\sqrt{1-\dfrac{2}{d_{G^{\prime}}(u)+d_{G^{\prime}}(z)}} \displaystyle-\sum_{u:u\in V(H_{1})\backslash\{x,u_{1}\}}\sqrt{1-\dfrac{2}{d_{G^{\prime}}(u)+d_{G^{\prime}}(w_{1})}}<0. Thus, \mathcal{ABS}(G)<\mathcal{ABS}(G^{\prime}) , a contradiction. Otherwise |V(H_{2})|=3 . In this case, \mathcal{ABS}(G)-\mathcal{ABS}(G^{\prime})< \displaystyle\displaystyle\sum_{w:w\in\{x,z\}}\sqrt{1-\dfrac{2}{d_{G}(w)+d_{G}(y)}}-\sum_{u:u\in V(H_{1})\backslash\{x\}}\sqrt{1-\dfrac{2}{d_{G^{\prime}}(u)+d_{G^{\prime}}(z)}} \displaystyle+\sum_{\underset{y^{\prime}\notin V(H_{2})}{y^{\prime}:y^{\prime}\sim y}}\sqrt{1-\dfrac{2}{d_{G}(y^{\prime})+d_{G}(y)}}-\sum_{\underset{y^{\prime}\notin V(H_{2})}{y^{\prime}:y^{\prime}\sim y}}\sqrt{1-\dfrac{2}{d_{G^{\prime}}(y^{\prime})+d_{G^{\prime}}(y)}} \displaystyle-\sqrt{1-\dfrac{2}{d_{G^{\prime}}(y^{\prime})+d_{G^{\prime}}(x)}}. (2.1) The sum of the first two terms in ( 2 ) is not positive, and it is easy to verify that the sum of the last three terms is negative. Thus, \mathcal{ABS}(G)<\mathcal{ABS}(G^{\prime}) , again a contradiction. Case 2: Suppose H_{1} and H_{2} do not share a common cut-vertex. Let x be a cut-vertex of G in H_{2} , and let y be a vertex of minimum degree in H_{2}\backslash\{x\} . Let G^{\prime} be the graph obtained from G by removing all the edges of H_{2} that are incident with either x or y , except the edge xy , and then joining each vertex of H_{2}\backslash\{x,y\} with every vertex in H_{1} . Then the cut-vertices of G and G^{\prime} are essentially the same, and by a similar argument to that of Case 1, we end up with a contradiction. Thus, \beta=2 . Since every block in G is a clique, G is either a path graph P_{n} or it can be formed by attaching one of the end vertices of a path P^{i} (with a length of at least 1) to a vertex u_{i} of the complete graph K_{n-p} (with vertex labels u_{1},u_{2},\ldots,u_{n-p} ) for 1\leq i\leq k , where 1\leq k\leq n-p . ∎ Graphs \mathbb{K}_{n}^{p} : Let n\geq 3 and 0\leq p\leq n-2 . If n\geq 2p , then \mathbb{K}_{n}^{p} is obtained by attaching p pendant vertices to p vertices of the complete graph K_{n-p} . Otherwise ( n<2p ), the graph \mathbb{K}_{n}^{p} is formed by attaching n-p-1 pendant vertices to n-p-1 vertices of K_{n-p} , and then a path of length 2p-n+1 is attached to the remaining one vertex of K_{n-p} . Figure 2.1 : Graphs \mathbb{K}_{n}^{p} , for n\geq 2p (left) and n<2p (right). Theorem 2.3 . Let G\in\mathbb{V}_{n}^{p}. Then \mathcal{ABS}(G)\leq\mathcal{ABS}(\mathbb{K}_{n}^{p}) , where