Maxima of the $A_\alpha$-spectral Radius of Graphs with Given Size and Minimum Degree $\delta \ge 2$

Zhang, Rong

doi:10.61091/jcmcc122-20

Abstract

1. Introduction
2. Preliminaries
3. Proofs of Theorems 1 and 2
Acknowledgments
Conflict of Interest
Funding Information

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 122
Pages: 243-253

Research article

Maxima of the $A_{α}$ -spectral Radius of Graphs with Given Size and Minimum Degree $δ \geq 2$

^¹

¹School of Mathematics and Statistics, Yancheng Teachers University, Yancheng, 224002, Jiangsu, P.R. China

Received: 07/06/2024
Accepted: 16/09/2024
Published: 30/09/2024

Copyright Link
License

Abstract

In this paper, we study the $A_{α}$ -spectral radius of graphs in terms of given size $m$ and minimum degree $δ \geq 2$ , and characterize the corresponding extremal graphs completely. Furthermore, we characterize extremal graphs having maximum $A_{α}$ -spectral radius among (minimally) $2$ -edge-connected graphs with given size $m$ .

Keywords: Size,

A_{α}

-spectral radius, Minimum degree, Extremal graph

1. Introduction

All graphs considered here are simple and undirected. For a graph $G$ , $A (G)$ denotes its adjacency matrix and $D (G)$ denotes the diagonal matrix of its degrees. The matrix $Q (G) = D (G) + A (G)$ is called the signless Laplacian matrix of $G$ . The largest eigenvalue of $A (G)$ is called the spectral radius of $G$ , and the largest eigenvalue of $Q (G)$ is called the signless Laplacian spectral radius of $G$ . For any real number $α \in [0, 1]$ , Nikiforov [1] defined the $A_{α}$ -matrix of $G$ as $A_{α} (G) = α D (G) + (1 - α) A (G)$ , which can be regarded as a common generalization of $A (G)$ and $Q (G)$ . The largest eigenvalue of $A_{α} (G)$ is called the $A_{α}$ -spectral radius of $G$ , denoted by $ρ_{α} (G)$ . For a connected graph $G$ , by the Perron-Frobenius theory of non-negative matrices [1], $ρ_{α} (G)$ has multiplicity one and there exists a unique positive unit eigenvector corresponding to $ρ_{α} (G)$ . We shall refor to such an eigenvector as the Perron vector of $A_{α} (G)$ .

The investigation on the extremal problems of the spectral radius and the signless Laplacian spectral radius of graphs is an important topic in the theory of graph spectra. For related results, one may refer to [2-5] and the references therein. Specially, the problem of characterizing the graph with maximal spectral radius for given size is initiated by Brualdi and Hoffman [6], and completely solved by Rowlinson [7]. For further investigation, one may refer to [8-13] and the references therein. Just recently, one of the hot topics in the study of the $Q$ -spectrum is to characterize the spectral extreme under the conditions of given size and graph parameters. Zhai et al. [14] determined the graph with maximal $Q -$ spectral radius among all graphs with given size, and characterized the graph with maximal $Q -$ spectral radius among all graphs with given size and clique number (resp., chromatic number). Lou et al. [15] determined the maximal signless Laplacian spectral radius (Laplacian spectral radius) of connected graphs with fixed size and diameter. For more results, one may refer to [16-19].

The $A_{α}$ -spectral radius of a graph has been widely concerned. However, the results on the $A_{α}$ -spectral radius under edge-condition are still relatively little known. Li and Qin [20] generalized the conclusion in [14] to $A_{α}$ -spectral radius for $1 / 2 \leq α \leq 1$ . Feng et al. [21] and Huang et al. [22] determined independently the graph having the maximum $A_{α}$ -spectral radius for $1 / 2 \leq α \leq 1$ among all connected graphs of size $m$ and diameter (at least) $d$ .

A friendship graph is one in which every pair of vertices has exactly one common neighbour, denoted by $F_{\frac{m}{3}}$ for given $m \equiv 0 (m o d 3)$ . The join of graphs $G$ and $H$ , denoted by $G \lor H$ , is the graph obtained from $G \cup H$ by joining each vertex of $G$ with every vertex of $H$ . In this paper, we completely characterize the graphs attaining the maximal $A_{α}$ -index among all graphs with given size $m$ and minimum degree $δ \geq 2$ for $\frac{1}{2} \leq α < 1$ .

Theorem 1. Let $\frac{1}{2} \leq α < 1$ and $G$ be a graph with $m$ edges and minimum degree $δ \geq 2$ , and $G_{1}, G_{2}$ be the graphs shown in Figure 1.

If $m \geq 24$ and $m \equiv 0 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (F_{\frac{m}{3}})$ , with equality if and only if $G = F_{\frac{m}{3}}$ .
If $m \geq 37$ and $m \equiv 1 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (G_{1})$ , with equality if and only if $G = G_{1}$ , where $G_{1} = K_{1} \lor (\frac{m - 7}{3} K_{2} \cup K_{1, 3})$ .
If $m \geq 29$ and $\equiv 2 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (G_{2})$ , with equality if and only if $G = G_{2}$ , where $G_{2} = K_{1} \lor (\frac{m - 5}{3} K_{2} \cup P_{3})$ .

A graph is $2$ -edge-connected if removing fewer than $2$ edges always leaves the remaining graph connected, and is minimally $2$ -edge-connected if it is $2$ -edge-connected and deleting any arbitrary chosen edge always leaves a graph which is not $2$ -edge-connected. For graphs of order $n$ , Chen and Guo [23] showed that $K_{2, n - 2}$ attained the maximal spectral radius among all the minimally $2$ -(edge)-connected graphs. Fan et al. [24] proved that $K_{3, n - 3}$ has the largest spectral radius over all minimally $3$ -connected graphs. For graphs of size $m$ , Guo and Zhang [16,19] gave sharp upper bounds on the $Q (L)$ -index of (minimally) $2$ -connected graphs with given size and characterized the corresponding extremal graphs completely. Noting that a connected graph having no cut edges is $2$ -edge-connected, we have following corollary.

Corollary 1. Let $\frac{1}{2} \leq α < 1$ and $G$ be a $2$ -edge-connected graph with $m$ edges.

If $m \geq 24$ and $m \equiv 0 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (F_{\frac{m}{3}})$ , with equality if and only if $G = F_{\frac{m}{3}}$ .
If $m \geq 37$ and $m \equiv 1 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (G_{1})$ , with equality if and only if $G = G_{1}$ , where $G_{1} = K_{1} \lor (\frac{m - 7}{3} K_{2} \cup K_{1, 3})$ .
If $m \geq 29$ and $\equiv 2 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (G_{2})$ , with equality if and only if $G = G_{2}$ , where $G_{2} = K_{1} \lor (\frac{m - 5}{3} K_{2} \cup P_{3})$ .

In this paper, we further study the problem of characterizing graphs among minimally $2$ -edge-connected graph with maximal $A_{α}$ – spectral radius. For $m \equiv 1 (m o d 3)$ , let $G_{3}$ (shown in Figure 2) be the graph obtained from the friendship graph $F_{\frac{m - 1}{3}}$ by subdividing an edge once. For $m \equiv 2 (m o d 3)$ , let $G_{4}$ (shown in Figure 2) be the graph obtained from the friendship graph $F_{\frac{m - 2}{3}}$ by subdividing an edge twice. Employing Theorem 1, we can prove the following theorem.

Theorem 2. Let $\frac{1}{2} \leq α < 1$ and $G$ be a minimally $2$ -edge-connected graph with $m$ edges.

If $m \geq 24$ and $m \equiv 0 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (F_{\frac{m}{3}})$ , with equality if and only if $G = F_{\frac{m}{3}}$ .
If $m \geq 37$ and $m \equiv 1 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (G_{3})$ , with equality if and only if $G = G_{3}$ .
If $m \geq 50$ and $m \equiv 2 (m o d 3)$ , then $ρ_{α} (G) \leq ρ_{α} (G_{4})$ , with equality if and only if $G = G_{4}$ .

The remainder of the paper is organized as follows. In Section 2, we recall some useful notions and lemmas that will be used later. In Section 3, we give proofs of Theorems 1 and 2 respectively.

2. Preliminaries

For a graph $G$ , $V (G)$ and $E (G)$ denote the vertex set and edge set of $G$ respectively, and $e (G) = | E (G) |$ denotes the number of edges in $G$ . For $v \in V (G),$ $d_{G} (v)$ or $d (v)$ denotes the degree of $v$ , $N_{G} (v)$ or $N (v)$ denotes the set of all neighbors of $v$ in $G$ , and $N [v] = N (v) \cup {v}$ . For a subset $S$ of $V (G)$ , $G [S]$ denotes the subgraph of $G$ induced by $S$ , $e (S)$ denotes the number of edges in $G [S]$ , and $N_{S} (v)$ denotes the set of all neighbors of $v$ in $S$ . For two disjoint subsets $S$ and $T$ of $V (G)$ , $e (S, T)$ denotes the number of edges with one endpoint in $S$ and the other in $T$ . Let $G - u v$ denote the graph obtained from $G$ by deleting the edge $u v \in E (G) .$ Similarly, $G + u v$ is the graph obtained from $G$ by adding an edge $u v \notin E (G),$ where $u, v \in V (G) .$ The average degree of the neighbors of a vertex $v_{i}$ of $G$ is $m (v_{i}) = \frac{1}{d (v_{i})} \sum_{v_{i} v_{j} \in E (G)} d (v_{j})$ . The degree sequence of $G$ is the non-increasing sequence of its vertex degrees. Whenever necessary, the vertices of $G$ can be renumbered so that $d_{i} \geq d_{i + 1}$ for $1 \leq i \leq n$ . In that case, we say that $G$ has degree sequence $(d_{1}, d_{2}, \dots, d_{n})$ , denoted by $D (G) = (d_{1}, d_{2}, \dots, d_{n})$ .

Let $G$ be a connected graph on $n$ vertices and $X = (x_{1}, x_{2}, \dots, x_{n})^{T} \in R^{n}$ . Then $X$ can be considered as a function defined on $V (G)$ , that is, each vertex $x_{i}$ is mapped to $x_{i} = x (v_{i})$ . One can find in [1] that $X^{T} A_{α} (G) X = (2 α - 1) \sum_{u \in V (G)} x_{u}^{2} d (u) + (1 - α) \sum_{u v \in E (G)} (x_{u} + x_{v})^{2},$ and for arbitrary unit vector $X \in R^{n}$ , $\begin{matrix} (1) & ρ_{α} (G) \geq X^{T} A_{α} (G) X, \end{matrix}$ with the equality if and only if $X$ is the Perron vector of $A_{α} (G)$ .

In order to prove our main results, we need the following lemmas.

Lemma 1. ([1])If $G$ is a graph with no isolated vertices, then $\begin{matrix} (2) & ρ_{α} (G) \leq max {α d (u) + (1 - α) m (u) | u \in V (G)} . \end{matrix}$

Lemma 2. ([1])Let $G$ be a graph with $n$ vertices and $Δ (G) = Δ$ . If $α \in [\frac{1}{2}, 1)$ , then $\begin{matrix} (3) & ρ_{α} (G) \geq α Δ + \frac{(1 - α)^{2}}{α} . \end{matrix}$ The equality holds if and only if $α = \frac{1}{2}$ and $G$ is the star $K_{1, n - 1}$ .

Lemma 3. ([1])Let $G$ be a connected graph with $α \in [0, 1)$ and $H$ be a proper subgraph of $G$ , then $ρ_{α} (H) < ρ_{α} (G)$ .

Lemma 4. ([25])Let $G$ be a connected graph, $u$ and $v$ be two vertices of $G$ . Suppose that $v_{i} \in N_{G} (v) ∖ N_{G} (u)$ $(1 \leq i \leq s)$ and $x = (x_{1}, x_{2}, \dots, x_{n})^{T}$ is the Perron vector of $Q (G)$ , where $x_{i}$ corresponds to the vertex $v_{i}$ $(1 \leq i \leq n)$ . Let $G^{*}$ be the graph obtained from $G$ by deleting the edges $v v_{i}$ and adding the edges $u v_{i}$ $(1 \leq i \leq s)$ . If $x_{u} \geq x_{v}$ , then $ρ_{α} (G) < ρ_{α} (G^{*})$ .

An internal path in some graph is a path $v_{0} v_{1} \dots v_{s}$ ( $s \geq 1$ , or $s \geq 3$ whenever $v_{s} = v_{0}$ ) such that $d (v_{0}) > 2$ , $d (v_{s}) > 2$ , and $d (v_{i}) = 2$ for $0 < i < s$ . Li, Chen and Meng [26] proved the following subdivision theorem.

Lemma 5. ([26])Let $G$ be a connected graph with $α \in [0, 1)$ and $u v$ be some edge on an internal path of $G$ . Let $G_{u v}$ denote the graph obtained from $G$ by subdivision of edge $u v$ into edges $u w$ and $w v$ . Then $ρ_{α} (G_{u v}) < ρ_{α} (G)$ .

A cycle $C$ of a graph $G$ is said to have a chord if there is an edge of $G$ that joins a pair of non-adjacent vertices of $C$ .

Lemma 6. ([11])If $G$ is a minimally $2$ -edge-connected graph, then no cycle of $G$ has a chord.

For a connected graph, Yu, Wu and Shu [27] gave a sharp upper bound on $Q$ -index in terms of its degree sequence. The authors of the current paper [28] generalized their result to $A_{α}$ -index of a connected graph. The following Lemma is a corollary of our result.

Lemma 7. ([28])Let $G$ be a simple connected graph with $n$ vertices and degree sequence $d_{1} \geq d_{2} \geq \dots \geq d_{n}$ . If $d_{1} \geq s \geq d_{2}$ , then $ρ_{α} (G) \leq A (d_{1}, s)$ , where $A (d_{1}, s) = \frac{1}{2} (α d_{1} + s + α - 1 + \sqrt{(s - α d_{1} + 1 - α)^{2} + 4 (1 - α) (d_{1} - s)}) .$

Lemma 8. Let $\frac{1}{2} \leq α < 1, m \geq 50$ , and $G_{5}$ be the graph shown in Figure 3. Then $ρ_{α} (G_{5}) < ρ_{α} (G_{4})$ .

Proof. Label the vertices is as shown in Figure 1. Let $X = (x_{w}, x_{1}, x_{2}, \dots, x_{\frac{2 m - 2}{3}}, x_{u})^{T}$ be a unit eigenvector corresponding to $ρ =: ρ_{α} (G_{5})$ where $x_{w}$ corresponds to $w$ and $x_{i}$ corresponds to $v_{i} (1 \leq i \leq \frac{2 m - 4}{3})$ and $x_{u}$ corresponds to $u$ . By the eigenvalue equation $ρ X = A_{α} (G_{5}) X$ , we have $x_{1} = x_{2} = x_{3} = x_{4}$ and $ρ x_{u} = 4 α x_{u} + 4 (1 - α) x_{1}$ . It follows that $x_{1} = \frac{ρ - 4 α}{4 (1 - α)} x_{u}$ . Define $Y = (y_{w}, y_{1}, y_{2}, \dots, y_{\frac{2 m - 4}{3}}, y_{u}, y_{v})^{T}$ such that $y_{w} = x_{w}, y_{i} = x_{i}$ for $1 \leq i \leq \frac{2 m - 4}{3}$ , and $y_{u} = y_{v} = \frac{\sqrt{2}}{2} x_{v}$ . Clearly, $\sum_{i = 1}^{\frac{2 m - 4}{3}} y_{i}^{2} + y_{w}^{2} + y_{u}^{2} + y_{v}^{2} = \sum_{i = 1}^{\frac{2 m - 4}{3}} x_{i}^{2} + x_{w}^{2} + x_{u}^{2} = 1.$ Noting that $m \geq 50$ and $d_{1} (G_{5}) = d (w) = \frac{2 m - 4}{3}$ , by Lemma 2, we have $ρ = ρ_{α} (G_{5}) > \frac{2 m - 4}{3} α \geq 16$ . By (1), we have $\begin{aligned} ρ_{α} (G_{4}) - ρ \geq & Y^{T} A_{α} (G_{7}) Y - X^{T} A_{α} (G_{6}) X \\ = & (2 α - 1) (- 2 x_{u}^{2}) + (1 - α) ((x_{1} + x_{2})^{2} + (x_{3} + \frac{x_{u}}{\sqrt{2}})^{2} \\ + (x_{4} + \frac{x_{u}}{\sqrt{2}})^{2} + (\frac{x_{u}}{\sqrt{2}} + \frac{x_{u}}{\sqrt{2}})^{2} - 4 (x_{1} + x_{u})^{2}) \\ = & (2 α - 1) (- 2 x_{u}^{2}) + (1 - α) ((2 \frac{ρ - 4 α}{4 (1 - α)} x_{u})^{2} + 2 (\frac{ρ - 4 α}{4 (1 - α)} x_{u} + \frac{x_{u}}{\sqrt{2}})^{2} \\ + 2 x_{u}^{2} - 4 (\frac{ρ - 4 α}{4 (1 - α)} x_{u} + x_{u})^{2}) \\ = & \frac{ρ^{2} - (4 \sqrt{2} α - 8 α - 4 \sqrt{2} + 16) ρ + 16 \sqrt{2} α^{2} - 24 α^{2} + 32 α - 16 \sqrt{2} α + 8}{8 (1 - α)} x_{u}^{2} \\ > & \frac{ρ^{2} - (4 \sqrt{2} α - 8 α - 4 \sqrt{2} + 16) ρ}{8 (1 - α)} x_{u}^{2} \\ > & 0. \end{aligned}$ Therefore $ρ_{α} (G_{5}) < ρ_{α} (G_{4})$ . This completes the proof.

3. Proofs of Theorems 1 and 2

Proof of Theorem 1. We may assume that $G$ is connected. Otherwise, suppose that $H_{i} (i = 1, 2, \dots, k)$ are $k$ connected components of $G$ , where $k \geq 2$ . Since $δ (G) \geq 2$ , then $δ (H_{i}) \geq 2 (1 \leq i \leq k)$ . For $i = 1, 2, \dots, k$ , let $v_{i}$ be a vertex of $H_{i}$ , and $G^{*}$ be the graph obtained from $H_{i}$ by identifying vertices $v_{i}$ . Clearly, $ρ_{α} (G) < ρ_{α} (G^{*})$ , and $G^{*}$ is a connected graph with $m$ edges and minimum degree $δ \geq 2$ . So, in order to complete the proof of Theorem 1, we may assume that $G$ is connected.

Furthermore, we may assume that $G$ is $2$ -edge-connected. Otherwise, suppose that $u_{1} v_{1} \in E (G)$ is a cut edge of $G$ . Since $δ (G) \geq 2$ , then there exist a path $P = u_{k} u_{k - 1} \dots u_{2} u_{1} v_{1} v_{2} \dots v_{l - 1} v_{l}$ , where $k, l \geq 1$ , such that $d (u_{k}) \geq 3 (d (v_{l}) \geq 3)$ and $u_{k} (v_{l})$ belongs to a cycle $C_{1} = u_{k} u_{k + 1} \dots u_{k + p} u_{k} (C_{2} = v_{l} v_{l + 1} \dots v_{l + q} v_{1})$ . Suppose that $| V (G) | = n$ . Let $X = (x_{u_{1}}, x_{u_{2}}, \dots, x_{u_{k + p}}, x_{v_{1}}, x_{v_{2}}, \dots, x_{v_{l + q}}, \dots, x_{n})^{T}$ be a unit eigenvector corresponding to $ρ_{α} (G)$ where $x_{u_{i}}$ corresponds to $u_{i} (1 \leq i \leq k + p)$ , $x_{v_{j}}$ corresponds to $v_{j} (1 \leq j \leq l + q)$ . If $x_{u_{k}} \geq x_{v_{l}}$ , let $G^{*} = G - v_{l} v_{l + 1} + u_{k} v_{l + 1}$ ; Otherwise, let $G^{*} = G - u_{k} u_{k + 1} + v_{l} u_{k + 1}$ . In the both cases, $G^{*}$ is a connected graph with $m$ edges and minimum degree $δ \geq 2$ and $u v$ is not a cut edge of $G^{*}$ any more. By Lemma 4, we have $ρ_{α} (G) < ρ_{α} (G^{*})$ . So we may assume that $G$ is $2$ -edge-connected.

Let $G_{m}^{2}$ denote the set of all $2$ -edge-connected graphs with $m$ edges. For $G \in G_{m}^{2}$ and $v \in V (G)$ , it is easy to see that $d (v) \geq 2$ and $G - v$ has no isolated vertices. Noting that $| E (G - v) | = m - d (v)$ , we have $d (v) \leq | V (G - v) | \leq 2 (m - d (v)) .$ It follows that $d (v) \leq \frac{2 m}{3}$ with equality if and only if $G = F_{\frac{m}{3}}$ .

For $G \in G_{m}^{2}$ , let $w$ be a vertex of $G$ such that $max_{u \in V (G)} {α d (u) + (1 - α) m (u)} = α d (w) + (1 - α) m (w) = α d (w) + \frac{1 - α}{d (w)} \sum_{w v \in E (G)} d (v) .$ Noting that $e (N (w)) \leq m - e (N (w), V (G) ∖ N (w))$ and $e (N (w), V (G) ∖ N (w)) \geq d (w)$ , we have $\sum_{w v \in E (G)} d (v) = 2 e (n (w)) + e (N (w), V (G) ∖ N (w)) \leq 2 m - d (w) .$ By Lemma 1, we have $\begin{matrix} (4) & ρ_{α} (G) \leq α d (w) + \frac{2 m}{d (w)} (1 - α) - 1 + α . \end{matrix}$

Let $m \geq 24$ and $m \equiv 0 (m o d 3)$ . It is easy to see that $F_{\frac{m}{3}} \in G_{m}^{2}$ . By Lemma 2, we have $ρ_{α} (F_{\frac{m}{3}}) > \frac{2 m α}{3} + \frac{(1 - α)^{2}}{α}$ .

If $d (w) = 2$ , noting that $e (N (w)) \leq 1$ , we have $\sum_{w v \in E (G)} d (v) = 2 e (N (w)) + e (N (w), V (G) ∖ N (w)) \leq 2 + m - 1 = m + 1.$ By (2), we have $ρ_{α} (G) \leq 2 α + \frac{m + 1}{2} (1 - α) \leq \frac{2 m α}{3} + \frac{(1 - α)^{2}}{α} < ρ_{α} (F_{\frac{m}{3}})$ for $m \geq 9$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = 3$ , noting that $e (N (w)) \leq 3$ , we have $\sum_{w v \in E (G)} d (v) = 2 e (N (w)) + e (N (w), V (G) ∖ N (w)) \leq 6 + m - 3 = m + 3.$ By (2), we have $q (G) \leq 3 α + \frac{m + 3}{3} (1 - α) \leq \frac{2 m α}{3} + \frac{(1 - α)^{2}}{α} < ρ_{α} (F_{\frac{m}{3}})$ for $m \geq 9$ and $\frac{1}{2} \leq α < 1$ .

If $4 \leq d (w) \leq \frac{2 m - 6}{3}$ , let $f (x) = α x + \frac{2 m}{x} (1 - α)$ . It is easy to see that the function $f (x)$ is convex for $x > 0$ and its maximum in any closed interval is attained at one of the ends of this interval. Combining this and (4), we have $\begin{aligned} ρ_{α} (G) & \leq max {4 α + \frac{2 m}{4} (1 - α), \frac{2 m - 6}{3} α + \frac{3 m}{m - 3} (1 - α)} - 1 + α \\ \leq \frac{2 m α}{3} + \frac{(1 - α)^{2}}{α} < ρ_{α} (F_{\frac{m}{3}}) . \end{aligned}$ for $m \geq 12$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m - 3}{3}$ , then $d_{1} = d_{1} (G) = \frac{2 m - 3}{3}$ . Let $| V (G - w) | = \frac{2 m - 3}{3} + s$ , then $2 m \geq \frac{2 m - 3}{3} + 2 (\frac{2 m - 3}{3} + s)$ . It follows that $0 \leq s \leq 1$ . This implies that $d_{2} = d_{2} (G) \leq 2 + 3 = 5$ . By Lemma 7, we have $ρ_{α} (G) \leq A (\frac{2 m - 3}{3}, 5) < \frac{2 m α}{3} + \frac{(1 - α)^{2}}{α} < ρ_{α} (F_{\frac{m}{3}})$ for $m \geq 24$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m}{3}$ , then $G = F_{\frac{m}{3}}$ , completing the proof of (i).
Let $m \geq 37$ and $m \equiv 1 (m o d 3)$ . It is easy to see that $G_{1} = K_{1} \lor (\frac{m - 2}{3} K_{2} \cup K_{1, 3}) \in G_{m}^{2}$ . By Lemma 2, we have $ρ_{α} (G_{1}) > \frac{2 m - 2}{3} α + \frac{(1 - α)^{2}}{α}$ .

For $2 \leq d (w) \leq \frac{2 m - 8}{3}$ , by similar reasoning as in the proof of (i), we can derived that $ρ_{α} (G) \leq \frac{2 m - 2}{3} α + \frac{(1 - α)^{2}}{α} < ρ_{α} (G_{1})$ for $m \geq 16$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m - 5}{3}$ , then $d_{1} = d_{1} (G) = \frac{2 m - 5}{3}$ . Let $| V (G - w) | = \frac{2 m - 5}{3} + s$ , then $2 m \geq \frac{2 m - 5}{3} + 2 (\frac{2 m - 5}{3} + s)$ . It follows that $0 \leq s \leq 2$ . This implies that $d_{2} = d_{2} (G) \leq 2 + 5 = 7$ . By Lemma 7, we have $ρ_{α} (G) \leq A (\frac{2 m - 5}{3}, 7) < \frac{2 m - 2}{3} α + \frac{(1 - α)^{2}}{α} < ρ_{α} (G_{1})$ for $m \geq 37$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m - 2}{3}$ , then $d_{1} = d_{1} (G) = \frac{2 m - 2}{3}$ . Let $| V (G - w) | = \frac{2 m - 2}{3} + s$ , then $2 m \geq \frac{2 m - 2}{3} + 2 (\frac{2 m - 2}{3} + s)$ . It follows that $0 \leq s \leq 1$ .

Figure 4 $G_{6}, G_{7}$

Case 1. $s = 0$ , it follows that $| V (G - w) | = \frac{2 m - 2}{3}$ . Noting that $| E (G) | = m$ , it is well known that $\sum_{i = 1}^{| V (G) |} d_{i} = 2 m$ . Since $δ \geq 2$ , then we known that $D (G)$ might be $(\frac{2 m - 2}{3}, 4, 2, 2, 2, 2, \dots, 2) or (\frac{2 m - 2}{3}, 3, 3, 2, 2, 2, \dots, 2) .$

If $D (G) = (\frac{2 m - 2}{3}, 4, 2, 2, 2, 2, \dots, 2)$ , then $G = G_{1}$ .

If $D (G) = (\frac{2 m - 2}{3}, 3, 3, 2, 2, 2, \dots, 2)$ , then $G = G_{6} = K_{1} \lor (\frac{m - 7}{3} K_{2} \cup p_{4})$ or $G = G_{7} = K_{1} \lor (\frac{m - 10}{3} K_{2} \cup 2 P_{3})$ , shown in Figure 4. Let $X = (x_{w}, x_{1}, x_{2}, x_{3}, x_{4}, \dots, x_{\frac{2 m - 2}{3}})^{T}$ be a unit eigenvector corresponding to $ρ_{α} (G_{6})$ where $x_{w}$ corresponds to $w$ and $x_{i}$ corresponds to $v_{i} (1 \leq i \leq \frac{2 m - 2}{3})$ . If $x_{2} \geq x_{3}$ , let $G^{*} = G_{6} - v_{4} v_{3} + v_{4} v_{2}$ ; Otherwise, let $G^{*} = G_{6} - v_{1} v_{2} + v_{1} v_{3}$ . In the both cases, $G^{*} = G_{1}$ . By Lemma 4, we have $ρ_{α} (G_{6}) < ρ_{α} (G_{1})$ . Applying Lemma 4 to the vertices $v_{2}$ and $v_{3}$ of $G_{7}$ , we can similarly derive that $ρ_{α} (G_{7}) < ρ_{α} (G_{1})$ .

Case 2. $s = 1$ , then $| V (G - w) | = \frac{2 m + 1}{3}$ . Noting that $| E (G) | = m$ , then $G$ has degree sequence $(\frac{2 m - 2}{3}, 2, 2, 2, 2, 2, \dots, 2)$ . It follows that $G = G_{3}$ . Noting that $w v_{2} v_{3} v_{1}$ is an internal path of $G_{3}$ , by Lemma 5, we have $ρ_{α} (G_{3}) < ρ_{α} (F_{\frac{m - 1}{3}})$ . Furthermore, noting that $F_{\frac{m - 1}{3}}$ is a proper subgraph of $G_{6}$ , by Lemma 3, we have $ρ_{α} (F_{\frac{m - 1}{3}}) < ρ_{α} (G_{6})$ . Therefore, we have $ρ_{α} (G_{3}) < ρ_{α} (G_{6}) < ρ_{α} (G_{1})$ .
Let $m \geq 29$ and $m \equiv 2 (m o d 3)$ . It is easy to see that $G_{2} \in G_{m}^{2}$ . By Lemma 2, we have $ρ_{α} (G_{2}) > \frac{2 m - 1}{3} α + \frac{(1 - α)^{2}}{α}$ .

For $2 \leq d (w) \leq \frac{2 m - 7}{3}$ , by similar reasoning as in the proof of (i), we can similarly derived that $ρ_{α} (G) < \frac{2 m - 1}{3} α + \frac{(1 - α)^{2}}{α} < ρ_{α} (G_{2})$ for $m \geq 14$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m - 4}{3}$ , let $| V (G - w) | = \frac{2 m - 4}{3} + s$ , then $2 m \geq \frac{2 m - 4}{3} + 2 (\frac{2 m - 4}{3} + s) .$ It follows that $s \leq 2$ . This implies that $d_{2} = d_{2} (G) \leq 2 + 4 = 6$ . By Lemma 7, we have $ρ_{α} (G) \leq A (\frac{2 m - 4}{3}, 6) \leq \frac{2 m - 1}{3} α + \frac{(1 - α)^{2}}{α} < ρ_{α} (G_{2})$ for $m \geq 29$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m - 1}{3}$ , let $| V (G - w) | = \frac{2 m - 1}{3} + s$ , then $2 m \geq \frac{2 m - 1}{3} + 2 (\frac{2 m - 1}{3} + s) .$ It follows that $s = 0$ . Noting that $| E (G) | = m$ , we known that $G$ has degree sequence $(\frac{2 m - 1}{3}, 3, 2, 2, 2, 2, \dots, 2)$ . It follows that $G = G_{2}$ , completing the proof of (iii).

Proof of Theorem 2. Let $H_{m}^{2}$ denote the set of all minimally $2$ -edge-connected graphs with $m$ edges.

Let $m \geq 24$ and $m \equiv 0 (m o d 3)$ . It is easy to see that $F_{\frac{m}{3}} \in H_{m}^{2} \subseteq G_{m}^{2}$ . By Theorem 1(i), we have $ρ_{α} (G) \leq ρ_{α} (F_{\frac{m}{3}})$ for $G \in H_{m}^{2}$ and the equality holds if and only if $G = F (\frac{m}{3})$ .
Let $m \geq 37$ and $m \equiv 1 (m o d 3)$ . It is easy to see that $G_{4} \in H_{m}^{2} \subseteq G_{m}^{2}$ . By Lemma 2, we have $ρ_{α} (G_{3}) > \frac{2 m - 2}{3} α + \frac{(1 - α)^{2}}{α}$ . From the proof of Theorem 1(ii), we know that $ρ_{α} (G) \leq \frac{2 m - 2}{3} α + \frac{(1 - α)^{2}}{α}$ for $G \in G_{m}^{2} ∖ {G_{1}, G_{3}, G_{6}, G_{7}}$ . This implies that $ρ_{α} (G) \leq ρ_{α} (G_{3})$ for $G \in H_{m}^{2}$ , and the equality holds if and only if $G = G_{3}$ .
Let $m \geq 50$ and $m \equiv 2 (m o d 3)$ . It is easy to see that $G_{4} \in H_{m}^{2} \subseteq G_{m}^{2}$ . By Lemma 2, we have $ρ_{α} (G_{4}) > \frac{2 m - 4}{3} α + \frac{(1 - α)^{2}}{α}$ . For $G \in H_{m}^{2}$ , let $w$ be a vertex of $G$ such that $max_{u \in V (G)} {α d (u) + (1 - α) m (u)} = α d (w) + (1 - α) m (w) = α d (w) + \frac{1 - α}{d (w)} \sum_{w v \in E (G)} d (v),$ where $2 \leq d (w) \leq \frac{2 m - 4}{3}$ .

For $2 \leq d (w) \leq \frac{2 m - 10}{3}$ , by similar reasoning as in the proof of Theorem 1(i), we can prove that $ρ_{α} (G) \leq α d (w) + (1 - α) m (w) \leq \frac{2 m - 4}{3} α + \frac{(1 - α)^{2}}{α} < ρ_{α} (G_{4})$ for $m \geq 20$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m - 7}{3}$ , let $| V (G - w) | = \frac{2 m - 7}{3} + s$ , then $2 m \geq \frac{2 m - 7}{3} + 2 (\frac{2 m - 7}{3} + s) .$ It follows that $0 \leq s \leq 3$ . This implies that $d_{2} = d_{2} (G) \leq 2 + 7 = 9$ . By Lemma 7, we have $ρ_{α} (G) \leq A (\frac{2 m - 7}{3}, 9) \leq \frac{2 m - 4}{3} α + \frac{(1 - α)^{2}}{α} < ρ_{α} (G_{4})$ for $m \geq 50$ and $\frac{1}{2} \leq α < 1$ .

If $d (w) = \frac{2 m - 4}{3}$ . let $| V (G - w) | = \frac{2 m - 4}{3} + s$ , then $2 m \geq \frac{2 m - 4}{3} + 2 (\frac{2 m - 4}{3} + s) .$ It follows that $0 \leq s \leq 2$ . We consider the following three cases.

Case 1. $s = 0$ , then $| V (G - w) | = \frac{2 m - 4}{3}$ and $| E (G - w) | = \frac{m + 4}{3}$ . Since $G$ is minimally $2$ -edge-connected, it follows that $G - w = p K_{2} \cup q K_{1}$ , where $p$ nd $q$ are nonnegative integers with $2 p + q = \frac{2 m - 4}{3}$ . This implies that $| E (G - w) | \leq \frac{m - 2}{3}$ , a contradiction.

Case 2. $s = 1$ . Let $V (G) ∖ N [w] = {u}$ . Then $| V (G - w) | = \frac{2 m - 1}{3}$ , and $D (G) = (\frac{2 m - 4}{3}, 4, 2, 2, 2, 2, \dots, 2)$ or $(\frac{2 m - 4}{3}, 3, 3, 2, 2, 2, \dots, 2)$ . If $D (G) = (\frac{2 m - 4}{3}, 4, 2, 2, 2, 2, \dots, 2)$ and there exist a vertex $v_{i} \in N (w)$ such that $d (v_{i}) = 4$ , then there exist at least two vertices $v_{j}, v_{k} \in N (w)$ such that $v_{i} v_{j}, v_{i} v_{k} \in E (G)$ . Obviously, we obtain a cycle $w v_{k} v_{i} v_{j} w$ with a chord $w v_{i}$ , a contradiction to Lemma 6.

If $D (G) = (\frac{2 m - 4}{3}, 4, 2, 2, 2, 2, \dots, 2)$ and $d (u) = 4$ , then $G = G_{5}$ , shown in Figure 3. By Lemma 8, we have $ρ_{α} (G_{5}) < ρ_{α} (G_{4})$ .

If $D (G) = (\frac{2 m - 4}{3}, 3, 3, 2, 2, 2, \dots, 2)$ , then exists a vertex $v_{i} \in N (w)$ such that $d (v_{i}) = 3$ . By Lemma 6, we know that $G [N (w)] = p K_{2} \cup q K_{1}$ . It follows that $u \in N (v_{i})$ . Suppose $N (v_{i}) = {w, u, v_{j}}$ . Noting that $d (u) \geq 2$ , we deduce that there exists another vertex $v_{k} \in N (w)$ such that $u v_{k} \in E (G)$ . If $v_{k} = v_{j}$ , we obtain a cycle $w v_{i} u v_{j} w$ with a chord $v_{i} v_{j}$ ; if $v_{k} \neq v_{j}$ , we obtain a cycle $w v_{j} v_{i} u v_{k} w$ with a chord $w v_{i}$ . This contracts Lemma 6.

Figure 5 $G_{8}$

Case 3. $s = 2$ . Let $V (G) ∖ N [w] = {u, v}$ . Then $| V (G - w) | = \frac{2 m + 2}{3}$ and the degree sequence of $G$ must be $(\frac{2 m - 4}{3}, 2, 2, 2, 2, 2, \dots, 2)$ . Noting that $E (G) = m$ and $d (w) = \frac{2 m - 4}{3}$ , it follows that $G = G_{4}$ or $G = G_{8}$ , shown in Figure <5. Applying Lemma 4 to vertices $u$ and $v$ of $G_{8}$ , we can derive $ρ_{α} (G_{8}) < ρ_{α} (G_{5})$ . By Lemma 8, we have $ρ_{α} (G_{5}) < ρ_{α} (G_{4})$ . Therefore $ρ_{α} (G_{8}) < ρ_{α} (G_{4})$ .

Combining the above arguments, we complete the proof.

Acknowledgments

The authors are grateful to the anonymous referees for valuable suggestions and corrections which result in an improvement of the original manuscript.

Conflict of Interest

The author declares no conflict of interest.

Funding Information

This research is supported by the National Natural Science Foundation of China (Nos. 12071411, 12171222).

References:

Nikiforov, V., 2017. Merging the A-and Q-spectral theories. Applicable Analysis and Discrete Mathematics, 11(1), pp.81-107.
Cvetković, D., Rowlinson, P. and Simić, S., 2010. An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge.
Nikiforov, V., 2011. Some new results in extremal graph theory. arXiv preprint arXiv:1107.1121.
Stanić, Z., 2015. Inequalities for Graph Eigenvalues (Vol. 423). Cambridge University Press.
Stevanoviâc, D., 2015. Spectral Radius of Graphs. Elsevier.
Brualdi, R.A. and Hoffman, A.J., 1985. On the spectral radius of (0, 1)-matrices. Linear Algebra and its Applications, 65, pp.133-146.
Rowlinson, P., 1988. On the maximal index of graphs with a prescribed number of edges. Linear Algebra and its Applications, 110, pp.43-53.
Bollobás, B. and Nikiforov, V., 2007. Cliques and the spectral radius. Journal of Combinatorial Theory, Series B, 97(5), pp.859-865.
Min, G., Lou, Z. and Huang, Q., 2022. A sharp upper bound on the spectral radius of C5-free/C6-free graphs with given size. Linear Algebra and its Applications, 640, pp.162-178.
Lin, H., Ning, B. and Wu, B., 2021. Eigenvalues and triangles in graphs. Combinatorics, Probability and Computing, 30(2), pp.258-270.
Lou, Z., Gao, M. and Huang, Q., 2022. On the spectral radius of minimally 2-(edge)-connected graphs with given size. arXiv preprint arXiv:2206.07872.
Rowlinson, P., 1989. On Hamiltonian graphs with maximal index. European Journal of Combinatorics, 10(5), pp.489-497.
Zhai, M., Lin, H. and Shu, J., 2021. Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs. European Journal of Combinatorics, 95, p.103322.
Zhai, M., Xue, J. and Lou, Z., 2020. The signless Laplacian spectral radius of graphs with a prescribed number of edges. Linear Algebra and its Applications, 603, pp.154-165.
Lou, Z., Guo, J.M. and Wang, Z., 2021. Maxima of L-index and Q-index: graphs with given size and diameter. Discrete Mathematics, 344(10), p.112533.
Guo, S.G. and Zhang, R., 2022. Sharp upper bounds on the Q-index of (minimally) 2-connected graphs with given size. Discrete Applied Mathematics, 320, pp.408-415.
Jia, H., Li, S. and Wang, S., 2022. Ordering the maxima of L-index and Q-index: Graphs with given size and diameter. Linear Algebra and its Applications, 652, pp.18-36.
Zhai, M., Xue, J. and Liu, R., 2022. An extremal problem on Q-spectral radii of graphs with given size and matching number. Linear and Multilinear Algebra, 70(20), pp.5334-5345.
Zhang, R. and Guo, S.G., 2022. Maxima of the Laplacian spectral radius of (minimally) 2-connected graphs with fixed size. Linear Algebra and its Applications, 651, pp.390-406.
Li, D. and Qin, R., 2021. The Aα-spectral radius of graphs with a prescribed number of edges for 12 ≤ α≤ 1. Linear Algebra and its Applications, 628, pp.29-41.
Feng, Z. and Wei, W., 2022. On the A α-spectral radius of graphs with given size and diameter. Linear Algebra and its Applications, 650, pp.132-149.
Huang, P., Li, J. and Shiu, W.C., 2022. Maximizing the Aα-spectral radius of graphs with given size and diameter. Linear Algebra and its Applications, 651, pp.116-130.
Chen, X. and Guo, L., 2019. On minimally 2-(edge)-connected graphs with extremal spectral radius. Discrete Mathematics, 342(7), pp.2092-2099.
Fan, D., Goryainov, S. and Lin, H., 2021. On the (signless Laplacian) spectral radius of minimally k-(edge)-connected graphs for small k. Discrete Applied Mathematics, 305, pp.154-163.
Nikiforov, V. and Rojo, O., 2018. On the α-index of graphs with pendent paths. Linear Algebra and its Applications, 550, pp.87-104.
Li, D., Chen, Y. and Meng, J., 2019. The Aα-spectral radius of trees and unicyclic graphs with given degree sequence. Applied Mathematics and Computation, 363, p.124622.
Yu, G., Wu, Y. and Shu, J., 2011. Sharp bounds on the signless Laplacian spectral radii of graphs. Linear Algebra and Its Applications, 434(3), pp.683-687.
Zhang, R. and Guo, S.G., 2023. An upper bound on the A_α-spectral radius of Hamiltonian graphs with given size, Advances in Mathematics,(China), accepted.

[1] Nikiforov, V., 2017. Merging the A-and Q-spectral theories. Applicable Analysis and Discrete Mathematics, 11(1), pp.81-107.

[2] Cvetković, D., Rowlinson, P. and Simić, S., 2010. An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge.

[3] Nikiforov, V., 2011. Some new results in extremal graph theory. arXiv preprint arXiv:1107.1121.

[4] Stanić, Z., 2015. Inequalities for Graph Eigenvalues (Vol. 423). Cambridge University Press.

[5] Stevanoviâc, D., 2015. Spectral Radius of Graphs. Elsevier.

[6] Brualdi, R.A. and Hoffman, A.J., 1985. On the spectral radius of (0, 1)-matrices. Linear Algebra and its Applications, 65, pp.133-146.

[7] Rowlinson, P., 1988. On the maximal index of graphs with a prescribed number of edges. Linear Algebra and its Applications, 110, pp.43-53.

[8] Bollobás, B. and Nikiforov, V., 2007. Cliques and the spectral radius. Journal of Combinatorial Theory, Series B, 97(5), pp.859-865.

[9] Min, G., Lou, Z. and Huang, Q., 2022. A sharp upper bound on the spectral radius of C5-free/C6-free graphs with given size. Linear Algebra and its Applications, 640, pp.162-178.

[10] Lin, H., Ning, B. and Wu, B., 2021. Eigenvalues and triangles in graphs. Combinatorics, Probability and Computing, 30(2), pp.258-270.

[11] Lou, Z., Gao, M. and Huang, Q., 2022. On the spectral radius of minimally 2-(edge)-connected graphs with given size. arXiv preprint arXiv:2206.07872.

[12] Rowlinson, P., 1989. On Hamiltonian graphs with maximal index. European Journal of Combinatorics, 10(5), pp.489-497.

[13] Zhai, M., Lin, H. and Shu, J., 2021. Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs. European Journal of Combinatorics, 95, p.103322.

[14] Zhai, M., Xue, J. and Lou, Z., 2020. The signless Laplacian spectral radius of graphs with a prescribed number of edges. Linear Algebra and its Applications, 603, pp.154-165.

[15] Lou, Z., Guo, J.M. and Wang, Z., 2021. Maxima of L-index and Q-index: graphs with given size and diameter. Discrete Mathematics, 344(10), p.112533.

[16] Guo, S.G. and Zhang, R., 2022. Sharp upper bounds on the Q-index of (minimally) 2-connected graphs with given size. Discrete Applied Mathematics, 320, pp.408-415.

[17] Jia, H., Li, S. and Wang, S., 2022. Ordering the maxima of L-index and Q-index: Graphs with given size and diameter. Linear Algebra and its Applications, 652, pp.18-36.

[18] Zhai, M., Xue, J. and Liu, R., 2022. An extremal problem on Q-spectral radii of graphs with given size and matching number. Linear and Multilinear Algebra, 70(20), pp.5334-5345.

[19] Zhang, R. and Guo, S.G., 2022. Maxima of the Laplacian spectral radius of (minimally) 2-connected graphs with fixed size. Linear Algebra and its Applications, 651, pp.390-406.

[20] Li, D. and Qin, R., 2021. The Aα-spectral radius of graphs with a prescribed number of edges for 12 ≤ α≤ 1. Linear Algebra and its Applications, 628, pp.29-41.

[21] Feng, Z. and Wei, W., 2022. On the A α-spectral radius of graphs with given size and diameter. Linear Algebra and its Applications, 650, pp.132-149.

[22] Huang, P., Li, J. and Shiu, W.C., 2022. Maximizing the Aα-spectral radius of graphs with given size and diameter. Linear Algebra and its Applications, 651, pp.116-130.

[23] Chen, X. and Guo, L., 2019. On minimally 2-(edge)-connected graphs with extremal spectral radius. Discrete Mathematics, 342(7), pp.2092-2099.

[24] Fan, D., Goryainov, S. and Lin, H., 2021. On the (signless Laplacian) spectral radius of minimally k-(edge)-connected graphs for small k. Discrete Applied Mathematics, 305, pp.154-163.

[25] Nikiforov, V. and Rojo, O., 2018. On the α-index of graphs with pendent paths. Linear Algebra and its Applications, 550, pp.87-104.

[26] Li, D., Chen, Y. and Meng, J., 2019. The Aα-spectral radius of trees and unicyclic graphs with given degree sequence. Applied Mathematics and Computation, 363, p.124622.

[27] Yu, G., Wu, Y. and Shu, J., 2011. Sharp bounds on the signless Laplacian spectral radii of graphs. Linear Algebra and Its Applications, 434(3), pp.683-687.

[28] Zhang, R. and Guo, S.G., 2023. An upper bound on the A_α-spectral radius of Hamiltonian graphs with given size, Advances in Mathematics,(China), accepted.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing