On Sombor Index of Unicyclic graphs with a fixed number of pendant vertices

Joyentanuj Das, Yogesh Kumar PrajapatyarXiv 2022 · DOI · arXiv

Abstract

The Sombor index is a topological index in graph theory defined by Gutman in 2021. In this article, we find the maximum Sombor index of unicyclic graphs with a fixed number of pendant vertices. We also provide the unique graph among the chosen class where the maximum Sombor index is attained.

Introduction

In chemical graph theory, researchers utilize "topological indices" to transform the structural properties of molecules—represented as graphs—into numerical values. These values are essential for predicting physical and chemical properties, such as boiling points or toxicity, through Quantitative Structure-Property Relationship (QSPR) models.

The Sombor index, introduced by Ivan Gutman in 2021, is a relatively new degree-based index inspired by Euclidean geometry. For an edge $uv$ in a graph, the index considers the degrees $d(u)$ and $d(v)$ as coordinates, calculating the sum of $\sqrt{d(u)^2 + d(v)^2}$ over all edges. While previous studies have explored the Sombor index for trees or graphs with fixed parameters like girth, this paper addresses the gap regarding unicyclic graphs (graphs containing exactly one cycle) with a fixed number of pendant vertices (vertices with only one connection).

Methodology

The authors employ a theoretical, proof-based approach using graph transformations. Rather than exhaustive computational testing, they utilize mathematical induction and a series of lemmas to demonstrate how specific structural changes influence the Sombor index.

Key techniques include:

  • Algebraic Inequalities: Establishing foundational lemmas to compare sums of square roots of squared degrees.
  • Edge Shifting: Proving that moving edges from lower-degree vertices to higher-degree vertices (centralization) consistently increases the Sombor index.
  • Structural Reduction: Systematically "pruning" and "re-planting" paths and edges to show that any unicyclic graph can be transformed into a specific "maximal" candidate without decreasing its Sombor index.

Key Results and Insights

The research culminates in identifying the unique structural configuration that maximizes the Sombor index for unicyclic graphs with $N$ vertices and $k$ pendant vertices. The Sombor index is maximized when the "degree contrast" between adjacent vertices is high, favoring "star-like" configurations over decentralized, path-like structures.

The unique extremal graph attaining the maximum Sombor index for $N > k + 3$.

According to Theorem 3.11, the maximum index is attained by a graph where the cycle is a triangle ($C_3$) and the pendant vertices are concentrated on a single "hub" vertex:

  • Cycle Minimization: To maximize the index, the internal cycle must be as small as possible ($C_3$), allowing for a higher concentration of edges on a single vertex.
  • Pendant Concentration: All $k$ pendant vertices must be attached to the same vertex on the cycle. Spreading these vertices across different nodes decreases the total index.
  • Structural Details: If $N > k + 3$, the graph consists of a $C_3$ where one vertex is attached to $k-1$ pendant edges and one path of length $N-k-2$, as illustrated in the figure above.

Conclusion

This study proves that for unicyclic graphs with a fixed number of pendant vertices, the Sombor index is uniquely maximized by a highly centralized structure. This geometric intuition follows from the index's definition: the function grows faster when degrees are concentrated into a "super-node."

Future work may involve identifying the minimum Sombor index for this class, which would likely involve the most decentralized configurations. Additionally, extending these results to bicyclic or tricyclic graphs could provide further insights into the structural behavior of this topological descriptor.

Summary updated

Abstract

The Sombor index is a topological index in graph theory defined by Gutman in 2021. In this article we find the maximum Sombor index of unicyclic graphs with a fixed number of pendant vertices. We also provide the unique graph among the chosen class where the maximum Sombor index is attained.
BibTeX
@misc{das2022sombor,
  author = {Joyentanuj Das and Yogesh Kumar Prajapaty},
  title = {{On Sombor Index of Unicyclic graphs with a fixed number of pendant vertices}},
  year = {2022},
  eprint = {2212.07732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2212.07732},
}
Figure