On the maximum $A_α$-spectral radius of unicyclic and bicyclic graphs with fixed girth or fixed number of pendant vertices

Joyentanuj Das, Iswar MahatoarXiv 2023 · DOI · arXiv

Abstract

For a connected graph $G$, let $A(G)$ be the adjacency matrix of $G$ and $D(G)$ be the diagonal matrix of the degrees of the vertices in $G$. The $A_α$-matrix of $G$ is defined as $A_α(G) = αD(G) + (1-α) A(G)$ for any $α\in [0,1]$. The largest eigenvalue of $A_α(G)$ is called the $A_α$-spectral radius of $G$. In this article, we characterize the graphs with maximum $A_α$-spectral radius among the class of unicyclic and bicyclic graphs of order $n$ with fixed girth $g$. Also, we identify the unique graphs with maximum $A_α$-spectral radius among the class of unicyclic and bicyclic graphs of order $n$ with $k$ pendant vertices.

Introduction

In spectral graph theory, the structural properties of a graph are often revealed through the eigenvalues of matrices associated with it. A particularly versatile tool in this field is the $A_\alpha$-matrix, introduced to provide a unified framework for studying the adjacency matrix ($A(G)$) and the signless Laplacian matrix ($Q(G)$). Defined as $A_\alpha(G) = \alpha D(G) + (1 - \alpha)A(G)$, this matrix transitions from the standard adjacency matrix at $\alpha = 0$ to a scaled signless Laplacian at $\alpha = 0.5$.

While extremal problems—identifying graphs that maximize or minimize the spectral radius—are well-documented for the specific cases of $\alpha = 0$ and $\alpha = 0.5$, the general behavior across the full range of $\alpha \in [0, 1]$ presents a more complex challenge. This research focuses on characterizing the "most influential" structures within unicyclic and bicyclic graph families, specifically looking at how constraints like girth (the length of the shortest cycle) and the number of pendant vertices (leaf nodes) influence the maximum $A_\alpha$-spectral radius.

Methodology: Structural Transformations

To identify the extremal graphs, the researchers employed a structural transformation approach. Rather than exhaustive computation, the study utilizes mathematical lemmas to prove that specific structural modifications monotonically increase the spectral radius. Key techniques include:

  • Edge Shifting: Relocating edges to concentrate the graph's degree at a single vertex, effectively increasing the local "influence" of that node.
  • Pendant Path Compression: Demonstrating that replacing long paths with multiple single pendant edges attached to a central hub increases the spectral radius.
  • Perron Vector Analysis: Leveraging the properties of the principal eigenvector (the Perron vector) to identify which vertices contribute most significantly to the spectral radius.
  • Subdivision Analysis: Examining how the introduction of new vertices along an edge (subdivision) impacts the overall spectral properties of the graph.

Characterizing Maximal Unicyclic Graphs

Unicyclic graphs contain exactly one cycle. The research identifies two primary configurations that maximize the $A_\alpha$-spectral radius depending on the constraints:

  1. Fixed Girth ($g$): For a graph of order $n$ and fixed girth $g$, the unique graph with the maximum spectral radius is $U_n(g)$. This structure consists of a cycle $C_g$ where all $n-g$ additional vertices are attached as pendant edges to a single vertex on the cycle.
  2. Fixed Pendant Vertices ($k$): When the number of pendant vertices $k$ is fixed, the maximal graph is $U_n(3, k)$. This configuration utilizes the smallest possible cycle (a triangle, $g=3$) with $k$ pendant edges attached to one vertex, while any remaining vertices form a specific path structure.

Characterizing Maximal Bicyclic Graphs

Bicyclic graphs, which contain two cycles, present more topological variety. They can be formed by two cycles sharing a vertex (coalesced) or two cycles sharing a path (theta graphs). The study's findings highlight the dominance of the "theta" structure in maximizing spectral radius:

  1. Fixed Girth ($g$): For $\alpha \in [1/2, 1)$, the maximal graph is a theta-graph $C(\lfloor g/2 \rfloor, \lceil g/2 \rceil, \lceil g/2 \rceil)$ with $n - \lceil 3g/2 \rceil + 1$ pendant edges attached to a vertex of degree 3. This indicates that for higher values of $\alpha$, the degree matrix $D(G)$ heavily weights the importance of high-degree vertices.
  2. Fixed Pendant Vertices ($k$): The unique maximal graph is $\mathfrak{B}_n^2(k)$, which consists of two triangles sharing an edge (forming a diamond graph), with all $k$ pendant edges concentrated on a single vertex of degree 3.

Discussion and Key Insights

The results reinforce a central theme in spectral graph theory: the "Hub Effect." To maximize the $A_\alpha$-spectral radius, a graph should ideally mimic a "star" configuration, where degrees are concentrated onto as few vertices as possible. Furthermore, minimizing cycle lengths (Cycle Minimization) consistently leads to higher spectral radii, as smaller cycles allow for higher degree concentration.

One limitation noted by the authors is that some bicyclic results are specifically proven for the range $\alpha \in [1/2, 1)$. When $\alpha < 1/2$, the influence of the adjacency matrix $A(G)$ is more pronounced than the degree matrix $D(G)$, which can occasionally lead to different extremal structures. Future work may extend these characterizations to tricyclic graphs or explore the corresponding "minimum" spectral radius problems for these classes.

Summary updated

Abstract

For a connected graph $G$, let $A(G)$ be the adjacency matrix of $G$ and $D(G)$ be the diagonal matrix of the degrees of the vertices in $G$. The $A_α$-matrix of $G$ is defined as \begin{align*} A_α(G) = αD(G) + (1-α) A(G) \quad \text{for any $α\in [0,1]$}. \end{align*} The largest eigenvalue of $A_α(G)$ is called the $A_α$-spectral radius of $G$. In this article, we characterize the graphs with maximum $A_α$-spectral radius among the class of unicyclic and bicyclic graphs of order $n$ with fixed girth $g$. Also, we identify the unique graphs with maximum $A_α$-spectral radius among the class of unicyclic and bicyclic graphs of order $n$ with $k$ pendant vertices.
BibTeX
@misc{das2023maximum,
  author = {Joyentanuj Das and Iswar Mahato},
  title = {{On the maximum $A\_α$-spectral radius of unicyclic and bicyclic graphs with fixed girth or fixed number of pendant vertices}},
  year = {2023},
  eprint = {2311.13364},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.13364},
}

Loading related content...

Figure