Sharp \(A_\alpha\)-spectral conditions for odd \([1,b]\)-factors when \(\alpha>1/2\)
May 30, 2026
Abstract
We solve, for all sufficiently large even orders, the problem proposed by Chen et al. on sharp \(A_\alpha\)-spectral conditions for the existence of odd \([1,b]\)-factors when \(\alpha>1/2\). Chen et al. showed that every connected graph of even order \(n\) with no odd \([1,b]\)-factor has \(A_\alpha\)-spectral radius at most \(\max_{1\le s\le k}\rho_\alpha(G_s)\), where \(G_s=K_s\nabla\left(K_{n-(b+1)s-1}\cup(bs+1)K_1\right)\) and \(k=\lfloor(n-2)/(b+1)\rfloor\). Thus the problem reduces to finding the graph with the largest \(A_\alpha\)-spectral radius among these obstruction graphs. We prove that, for every \(\alpha\in(1/2,1)\), \(\max_{1\le s\le k}\rho_\alpha(G_s)=\max\{\rho_\alpha(G_1),\rho_\alpha(G_k)\}\). Moreover, for each fixed odd \(b\ge 3\) and every even \(n\ge N_b=(b+1)\max\{2b+3,14\}+2\), there exists a unique \(\alpha=\alpha_\ast(n,b)\in(1/2,1)\) at which \(\rho_\alpha(G_1)=\rho_\alpha(G_k)\). Consequently, \(G_1\) is the unique extremal graph for \(1/2<\alpha<\alpha_\ast(n,b)\), both \(G_1\) and \(G_k\) are extremal at \(\alpha=\alpha_\ast(n,b)\), and \(G_k\) is the unique extremal graph for \(\alpha_\ast(n,b)<\alpha<1\). This gives the exact \(A_\alpha\)-spectral threshold, together with the sharp exceptional graphs, for odd \([1,b]\)-factors when \(\alpha>1/2\) and \(n\ge N_b\).
1 Introduction↩︎
For a graph \(G\), let \(A(G)\) and \(D(G)\) be its adjacency matrix and its diagonal degree matrix, respectively. Nikiforov [1] introduced the \(A_{\alpha}\)-matrix, defined by \[A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G),\qquad \alpha\in[0,1].\] This matrix interpolates between the adjacency matrix, one half of the signless Laplacian, and the degree matrix. We write \(\rho_{\alpha}(G)\) for the spectral radius of \(A_{\alpha}(G)\).
Let \(b\ge 1\) be odd. An odd \([1,b]\)-factor of \(G\) is a spanning subgraph \(H\) such that the degree of every vertex \(v\in V(H)\) in \(H\), denoted by \(d_H(v)\), is odd, and \[1\le d_H(v)\le b\qquad \text{for all }v\in V(G).\] Amahashi [2] proved that \(G\) contains an odd \([1,b]\)-factor if and only if \[o(G-S)\le b|S|\qquad \text{for every }S\subseteq V(G),\] where \(o(G-S)\) denotes the number of odd components (i.e. components that have an odd number of vertices) of \(G-S\). This criterion is the starting point of the spectral approach to odd factors.
The interplay between spectral radius and the existence of graph factors has attracted considerable attention in recent years. For instance, for the adjacency spectral radius, O [3] obtained sharp conditions for perfect matchings, and sharp conditions for odd \([1,b]\)-factors and general \([a,b]\)-factors were subsequently obtained in [4]–[6]. For regular graphs, Kim et al. [7] and O [8] gave eigenvalue conditions for odd \([1,b]\)-factors and general \([a,b]\)-factors respectively. For the \(A_{\alpha}\)-spectral radius, Zhao et al. [9] studied perfect matchings, and Chen et al. [10] solved the odd \([1,b]\)-factor problem for \(\alpha\in[0,\frac{1}{2}]\). For other related \(A_{\alpha}\)-spectral factor results, such as conditions for path-factors, (fractional) \([a,b]\)-factors, extendability, and some other factor problems, readers may refer to [11]–[15].
In this paper, we study the following problem proposed by Chen et al. [10].
Problem 1.5. Let \(\alpha\in(\frac{1}{2},1)\) and let \(G\) be a connected graph of even order \(n\). Investigate the lower bound on \(\rho_{\alpha}(G)\) to guarantee the existence of an odd \([1,b]\)-factor.
In [10], the problem is reduced to the graph family \[\label{eq:introGs} G_s=K_s\nabla\left(K_{n-(b+1)s-1}\cup(bs+1)K_1\right), \qquad 1\le s\le k\mathrel{\vcenter{:}}=\left\lfloor\frac{n-2}{b+1}\right\rfloor.\tag{1}\] In other words, if \(G\) is a connected graph of even order \(n\) with no odd \([1,b]\)-factors, then \[\rho_{\alpha}(G)\le\max_{1\le s\le k}\rho_{\alpha}(G_s).\] Hence Problem 1.5 is reduced to the comparison of \[\Lambda_s(\alpha;n,b)\mathrel{\vcenter{:}}=\rho_\alpha(G_s), \qquad 1\le s\le k.\] For \(\alpha\le\frac{1}{2}\), [10] shows that \(G_1\) is extremal for all \(n>b+2+\alpha+\frac{2(b+1)(b+2-\alpha)^2}{b}\). The case \(\alpha>\frac{1}{2}\) is the part left open there and is solved in this paper for \(n\ge N_b\mathrel{\vcenter{:}}=(b+1)\max\{2b+3,14\}+2\).
Our first main result shows that, once the problem is reduced to the family \(\{G_s\}_{s=1}^k\), it is enough to compare the two graphs \(G_1\) and \(G_k\).
Theorem 1. Let \(n\) be even and let \(b\ge 3\) be odd. Set \(k=\left\lfloor\frac{n-2}{b+1}\right\rfloor\). Assume \(k\ge 1\). Then for every \(\alpha\in(\frac{1}{2},1)\), \[\max_{1\le s\le k}\rho_{\alpha}(G_s)=\max\{\rho_{\alpha}(G_1),\rho_{\alpha}(G_k)\}.\]
Our second main result determines the unique value of \(\alpha\) at which \(\rho_{\alpha}(G_1)=\rho_{\alpha}(G_k)\), for all even \(n\) above an explicit threshold.
Theorem 2. Let \(n\) be even and let \(b\ge 3\) be odd. Then, for every even \(n\ge N_b\), there exists a unique \(\alpha_\ast(n,b)\in(\frac{1}{2},1)\) such that \[\rho_{\alpha}(G_1)=\rho_{\alpha}(G_k).\] More precisely, we have \[\begin{align} \alpha_\ast(n,b) &=1-\frac{(b+1)^2}{bn}+\frac{(b+1)^2\left(b^3+b\ell-b-1\right)}{b^3n^2}+O(n^{-3}), \\ \ell&=n-(b+1)k-1. \end{align}\] Consequently, for \(\frac{1}{2}<\alpha<\alpha_\ast(n,b)\), \(G_1\) is the unique extremal graph in \(\{G_s\}_{s=1}^k\); for \(\alpha=\alpha_\ast(n,b)\), both \(G_1\) and \(G_k\) are the extremal graphs in \(\{G_s\}_{s=1}^k\); for \(\alpha_\ast(n,b)<\alpha<1\), \(G_k\) is the unique extremal graph in \(\{G_s\}_{s=1}^k\).
Combining the two theorems above yields the following theorem.
Theorem 3. Let \(G\) be a connected graph of even order \(n\ge N_b=(b+1)\max\{2b+3,14\}+2\). Let \(b\ge 3\) be odd and let \(\alpha_\ast(n,b)\) be the parameter determined from 2. Then:
If \(\frac{1}{2}<\alpha<\alpha_\ast(n,b)\) and \[\rho_{\alpha}(G)\ge\rho_{\alpha}(G_1),\] then \(G\) contains an odd \([1,b]\)-factor unless \(G\cong G_1\).
If \(\alpha_\ast(n,b)<\alpha<1\) and \[\rho_{\alpha}(G)\ge\rho_{\alpha}(G_k),\] then \(G\) contains an odd \([1,b]\)-factor unless \(G\cong G_k\).
If \(\alpha=\alpha_\ast(n,b)\) and \[\rho_{\alpha}(G)\ge\rho_{\alpha}(G_1)=\rho_{\alpha}(G_k),\] then \(G\) contains an odd \([1,b]\)-factor unless \(G\cong G_1\) or \(G\cong G_k\).
The structure of this paper is as follows. [sec:reduction,sec:quotient] collect the reduction and quotient-matrix tools. 4 proves that only \(G_1\) and \(G_k\) need to be compared, and 5 compares \(G_1\) and \(G_k\) and determines the value of \(\alpha\) for which they have the same spectral radius.
2 Preliminaries and the graph family \(G_s\)↩︎
All graphs in this paper are simple, finite, undirected, and connected, unless stated otherwise. We write \(\nabla\) for the join of two graphs and \(\cup\) for the disjoint union of two graphs. Throughout the paper, we suppose that \(n\) is even and \(b\) is odd. This is because if \(b\) is even, then an odd \([1,b]\)-factor is equivalent to an odd \([1,b-1]\)-factor. Moreover, if \(b=1\), this is exactly the perfect-matching case and has been treated by Zhao et al. [9]. Hence, in this paper, we always assume that \(b\ge 3\).
We begin with Amahashi’s criterion.
Lemma 1 (Amahashi [2]). Let \(G\) be a graph and let \(b\) be a positive odd integer. Then \(G\) contains an odd \([1,b]\)-factor if and only if \[o(G-S)\le b|S|\qquad \text{for every }S\subseteq V(G).\]
We first verify that each graph in this family we stated is indeed an obstruction.
Lemma 2. For every \(1\le s\le k\), the graph \[G_s=K_s\nabla\left(K_{n-(b+1)s-1}\cup(bs+1)K_1\right)\] contains no odd \([1,b]\)-factor.
Proof. Let \(S=V(K_s)\). Then \[G_s-S=K_{r_s}\cup t_sK_1, \qquad \text{where }r_s\mathrel{\vcenter{:}}= n-(b+1)s-1, \,t_s\mathrel{\vcenter{:}}= bs+1.\] Since \(n\) is even and \(b+1\) is even, \(r_s\) is odd. Hence \(G_s-S\) has exactly \(t_s+1=bs+2\) odd components. Therefore \[o(G_s-S)=bs+2>bs=b|S|.\] By 1, \(G_s\) has no odd \([1,b]\)-factor. ◻
The next two lemmas are part of the argument of Chen et al. One can verify that none of these steps depends on \(\alpha\le\frac{1}{2}\), so the same proof works for all \(\alpha\in[0,1)\).
Lemma 3. Let \(\alpha\in[0,1)\) and let \(G\) be a connected graph of even order \(n\) with no odd \([1,b]\)-factor. Set \[k\mathrel{\vcenter{:}}=\left\lfloor\frac{n-2}{b+1}\right\rfloor, \qquad G_s=K_s\nabla\left(K_{n-(b+1)s-1}\cup(bs+1)K_1\right) \quad (1\le s\le k).\] Then there exists \(s\in\{1,\dots,k\}\) such that \[\rho_{\alpha}(G)\le\rho_{\alpha}(G_s).\] Equivalently, \[\rho_{\alpha}(G)\le\max_{1\le s\le k}\rho_{\alpha}(G_s).\]
Proof. This is proved in [10]. ◻
The next lemma proves the sharpness of the obstruction graph family \(\{G_i\}_{i=1}^k\).
Lemma 4. Let \(\alpha\in[0,1)\) and let \(G\) be a connected graph of even order \(n\) with no odd \([1,b]\)-factor. Let \(k\) and \(G_s\) be as in 3. If \[\rho_{\alpha}(G)\ge\max_{1\le i\le k}\rho_{\alpha}(G_i),\] then there exists \(s\in\{1,\dots,k\}\) such that \(G\cong G_s\).
Proof. This condition forces equality in 3, and the equality clauses in [10] therefore give \(G\cong G_s\) for some \(s\) with \(\rho_{\alpha}(G_s)=\max_{1\le i\le k}\rho_{\alpha}(G_i)\). ◻
For later convenience, we fix the following notation.
Definition 1. Define \[k\mathrel{\vcenter{:}}=\left\lfloor\frac{n-2}{b+1}\right\rfloor, \qquad r_s\mathrel{\vcenter{:}}= n-(b+1)s-1, \qquad t_s\mathrel{\vcenter{:}}= bs+1, \qquad \Lambda_s(\alpha)\mathrel{\vcenter{:}}=\rho_{\alpha}(G_s),\] where \(G_s\) is given by 1 . With this notation, \(G_s=K_s\nabla(K_{r_s}\cup t_sK_1)\). For later convenience, we also write \[\ell\mathrel{\vcenter{:}}= r_k=n-(b+1)k-1.\] It holds that \(1\le \ell\le b\) and \(\ell\) is odd.
3 Quotient matrices and estimates for the spectral radii↩︎
This section reduces \(\rho_{\alpha}(G_s)\) to the Perron root of a \(3\times 3\) quotient matrix. Moreover, to compare \(\rho_{\alpha}(G_1)\) and \(\rho_{\alpha}(G_k)\), we obtain two expansions of \(\Lambda_s\): one for fixed \(s\), and one for the case \(\epsilon n\le s\le k\).
We start by introducing the concept of a quotient matrix.
Definition 2. Let \(M=(m_{uv})\) be an \(n\times n\) matrix whose rows and columns are indexed by a finite set \(X\), and let \(\pi=\{X_1,X_2,\dots,X_t\}\) be a partition of \(X\). We say that \(\pi\) is an equitable partition of \(M\) if, for every \(i,j\in\{1,2,\dots,t\}\), the quantity \[b_{ij}=\sum_{v\in X_j}m_{uv}\] is independent of the choice of \(u\in X_i\). In this case, the \(t\times t\) matrix \(M/\pi\mathrel{\vcenter{:}}=(b_{ij})\) is called the quotient matrix of \(M\) with respect to \(\pi\).
An important property of quotient matrices is that if the original matrix is nonnegative and irreducible, then the quotient matrix has the same spectral radius as the original matrix.
Lemma 5 ([16]). Let \(M/\pi\) be the quotient matrix of \(M\) with respect to \(\pi\). Then \[\mathop{\mathrm{Spec}}(M/\pi)\subseteq\mathop{\mathrm{Spec}}(M).\] Moreover, if \(M\) is nonnegative and irreducible, then \[\rho(M/\pi)=\rho(M).\]
We show that an equitable partition for \(A(G)\) is also equitable for \(A_{\alpha}(G)\).
Lemma 6. Let \(G\) be a graph, \(A(G)\) be its adjacency matrix, and let \(\pi=\{V_1,\dots,V_t\}\) be an equitable partition of \(A(G)\). Let \(A(G)/\pi\eqqcolon B(G)=(b_{ij})\) be the quotient matrix of \(A(G)\) with respect to \(\pi\). Then \(\pi\) is also equitable for \(A_{\alpha}(G)\), and the corresponding quotient matrix is \[A_{\alpha}(G)/\pi=\alpha\Delta+(1-\alpha)B(G)\eqqcolon B_{\alpha}(G),\] where \(\Delta=\mathop{\mathrm{diag}}(d_1,\dots,d_t)\), and \[d_i=\sum_{j=1}^t b_{ij}\] are the row sums of \(B\). Moreover, if \(G\) is connected and \(\alpha<1\), then \[\rho(B_{\alpha}(G))=\rho(A_{\alpha}(G)).\]
Proof. Let \(u\in V_i\). Since \(\pi\) is equitable for \(A(G)\), the number of neighbors of \(u\) in \(V_j\) is \(b_{ij}\), which is independent of the choice of \(u\in V_i\). Hence every vertex in \(V_i\) has the same degree \[d_i=\sum_{j=1}^t b_{ij}.\] Therefore, for \(u\in V_i\), the sum of the entries of the row of \(A_{\alpha}(G)\) indexed by \(u\) over the block \(V_j\) is \[\sum_{v\in V_j}(A_{\alpha}(G))_{uv}= \begin{cases} \alpha d_i+(1-\alpha)b_{ii}, & j=i,\\ (1-\alpha)b_{ij}, & j\ne i. \end{cases}\] This depends only on \(i\) and \(j\), so \(\pi\) is also equitable for \(A_{\alpha}(G)\). The corresponding quotient matrix is \[A_{\alpha}(G)/\pi=\alpha\Delta+(1-\alpha)B(G)=B_{\alpha}(G).\] If \(G\) is connected and \(\alpha<1\), then \(A_{\alpha}(G)\) is nonnegative and irreducible, so 5 gives \[\rho(B_{\alpha}(G))=\rho(A_{\alpha}(G)).\] This completes the proof. ◻
To obtain an equitable partition for \(A(G_s)\), we fix \(1\le s\le k\) and partition \(V(G_s)=V\left(K_s\nabla\left(K_{r_s}\cup t_sK_1\right)\right)\) into three parts: \[V_1=V(K_s),\qquad V_2=V(K_{r_s}),\qquad V_3=V(t_sK_1).\] One can verify that the partition \(\{V_1,V_2,V_3\}\) is equitable for \(A(G_s)\), hence also equitable for \(A_{\alpha}(G_s)\) by 6. For later convenience, write \[\label{eq:delta-uvw} \beta\mathrel{\vcenter{:}}= 1-\alpha, \qquad u_s\mathrel{\vcenter{:}}= n-1-\beta(n-s), \qquad v_s\mathrel{\vcenter{:}}= n-bs-2-\beta s, \qquad w_s\mathrel{\vcenter{:}}= s-\beta s.\tag{2}\] A direct computation shows that the corresponding quotient matrix is \[B_s\mathrel{\vcenter{:}}= B_\alpha(G_s)=\begin{bmatrix} u_s & \beta r_s & \beta t_s\\ \beta s & v_s & 0\\ \beta s & 0 & w_s \end{bmatrix}.\] By setting \(P_s=\mathop{\mathrm{diag}}(\sqrt{s},\sqrt{r_s},\sqrt{t_s})\), \(B_s\) is similar and thus cospectral to the real symmetric matrix \[\widetilde{B}_s=P_s B_s P_s^{-1}= \begin{bmatrix} u_s & \beta\sqrt{s r_s} & \beta\sqrt{s t_s}\\ \beta\sqrt{s r_s} & v_s & 0\\ \beta\sqrt{s t_s} & 0 & w_s \end{bmatrix}.\] We then have \[\Lambda_s(\alpha)\mathrel{\vcenter{:}}=\rho_{\alpha}(G_s)=\rho(B_s)=\rho(\widetilde{B}_s).\]
We now derive the characteristic equation satisfied by \(\rho(\widetilde{B}_s)\).
Lemma 7. For \(1\le s\le k\), \(\Lambda_s=\Lambda_s(\alpha)\) satisfies \[\label{eq:schur-poly} (\Lambda_s-u_s)(\Lambda_s-v_s)(\Lambda_s-w_s)-\beta^2 s\left[r_s(\Lambda_s-w_s)+t_s(\Lambda_s-v_s)\right]=0.\tag{3}\] Moreover, we have \[\label{eq:schur} \Lambda_s=u_s+\beta^2 s\left(\frac{r_s}{\Lambda_s-v_s}+\frac{t_s}{\Lambda_s-w_s}\right).\tag{4}\]
Proof. 3 is simply the characteristic equation \(\det(\Lambda_sI-\widetilde{B}_s)=0\). Moreover, since \(\widetilde{B}_s\) is nonnegative and irreducible, by the Perron–Frobenius theorem, its Perron root, which is exactly its spectral radius \(\Lambda_s\), satisfies \(\Lambda_s>\max\{u_s,v_s,w_s\}\). Therefore we may divide 3 by \((\Lambda_s-v_s)(\Lambda_s-w_s)\) and get 4 . ◻
This gives an upper bound for \(\Lambda_s\) when \(u_s>\max\{v_s,w_s\}\), which will be useful later.
Lemma 8. Write \[\Lambda_s^{+}\mathrel{\vcenter{:}}= u_s+\beta^2s\left(\frac{r_s}{u_s-v_s} +\frac{t_s}{u_s-w_s}\right).\] Then if \(u_s-v_s>0\) and \(u_s-w_s>0\), it holds that \(\Lambda_s\le\Lambda_s^{+}\).
Proof. Define the function \[f_s(x)\mathrel{\vcenter{:}}= u_s+\beta^2 s\left(\frac{r_s}{x-v_s}+\frac{t_s}{x-w_s}\right), \qquad x>\max\{v_s,w_s\}.\] By 7, \(\Lambda_s=f_s(\Lambda_s)\). Moreover, \[f_s'(x)=-\beta^2 s\left(\frac{r_s}{(x-v_s)^2}+\frac{t_s}{(x-w_s)^2}\right)<0,\] so \(f_s\) is strictly decreasing on its domain.
If \(u_s-v_s>0\) and \(u_s-w_s>0\), then \(u_s>\max\{v_s,w_s\}\), so \(u_s\) lies in the domain of \(f_s\). By 7, we have \(\Lambda_s>u_s\). Therefore the monotonicity of \(f_s\) yields \[\Lambda_s=f_s(\Lambda_s)\le f_s(u_s)=\Lambda_s^{+}.\] This completes the proof. ◻
We next record two estimates of \(\Lambda_s\): one for fixed \(s\), and one for the range \(\epsilon n\le s\le k\).
Theorem 4. Fix an odd integer \(b\ge 3\) and let \(n\to\infty\) through even integers. Set \(c=n(1-\alpha)\). Then the following estimates hold.
Fix a positive integer \(s\), and let \(I\) be a fixed compact interval contained in \((bs+1,+\infty)\). Then, uniformly for \(c\in I\), \[\Lambda_s\left(1-\frac{c}{n}\right) =n-bs-2-\frac{cs}{n}+\frac{c^2s}{(c-bs-1)n}+O(n^{-2}).\] The constant in the \(O(n^{-2})\) term may depend on \(b\), \(s\), and \(I\), but is independent of \(c\) and \(n\).
Fix \(\epsilon\in(0,\frac{1}{b+1})\). If \(\epsilon n\le s\le k\), then, uniformly for \(c\) in any fixed bounded interval \(J\subset(0,+\infty)\), \[\label{eq:theta-expansion} \Lambda_s\left(1-\frac{c}{n}\right) =n-1-c+\frac{cs}{n} +\frac{c^2}{n}h_b\left(\frac{s}{n}\right)+O(n^{-2}),\tag{5}\] where \[h_b(\theta)\mathrel{\vcenter{:}}=\frac{1-(b+1)\theta}{b} +\frac{b\theta^2}{1-\theta}.\] The constant in the \(O(n^{-2})\) term may depend on \(b\), \(\epsilon\), and \(J\), but is independent of \(c\), \(s\), and \(n\).
Proof. Recall from 4 that, after setting \(\beta=c/n\), \[\label{eq:schur-c} \Lambda_s=u_s+\frac{c^2s}{n^2} \left(\frac{r_s}{\Lambda_s-v_s}+\frac{t_s}{\Lambda_s-w_s}\right).\tag{6}\]
We first prove the first estimate. Set \[\label{eq:delta-s} \Delta_s\mathrel{\vcenter{:}}= c-bs-1>0,\tag{7}\] and write \(\Lambda_s=v_s+r\) with \(r>0\). Since \(u_s-v_s=-(c-bs-1)+O(n^{-1})\), 6 gives \[\label{eq:schur-r-c-2} r^2+\left(\Delta_s-\frac{2cs}{n}\right)r =\frac{c^2sr_s}{n^2} +\frac{c^2st_s\,r}{n^2(v_s+r-w_s)}.\tag{8}\] Here \[r_s=n+O(1),\qquad t_s=O(1),\qquad v_s-w_s=n+O(1).\] Since \(I\) is compact and disjoint from \(bs+1\), there exists \(\eta>0\) such that \(\Delta_s\ge\eta\) on \(I\). Thus, for all large \(n\), \[r^2+\frac{\eta}{4}r\le \frac{C}{n},\] and hence \(r=O(n^{-1})\). Returning to 8 , we get \[\Delta_s r=\frac{c^2s}{n}+O(n^{-2}),\] and therefore \[r=\frac{c^2s}{(c-bs-1)n}+O(n^{-2}).\] Since \(v_s=n-bs-2-cs/n\), the first estimate follows.
We now prove the second estimate. Let \(c\) range in a fixed bounded interval \(J\subset(0,+\infty)\) and put \[\theta_s\mathrel{\vcenter{:}}=\frac{s}{n} \in\left[\epsilon,\frac{1}{b+1}\right].\] Write \(\Lambda_s=u_s+r\) with \(r>0\), and define \[\Gamma_s\mathrel{\vcenter{:}}= u_s-v_s=b\theta_sn-c+1+2c\theta_s, \qquad \Omega_s\mathrel{\vcenter{:}}= u_s-w_s=(1-\theta_s)n-c-1+2c\theta_s.\] Both \(\Gamma_s\) and \(\Omega_s\) are bounded from above and below by positive constant multiples of \(n\), uniformly for \(c\in J\) and \(\epsilon n\le s\le k\). Hence 6 gives \(r=O(n^{-1})\). Moreover, \[\frac{r_s}{\Gamma_s+r}=\frac{r_s}{\Gamma_s}+O(n^{-2}), \qquad \frac{t_s}{\Omega_s+r}=\frac{t_s}{\Omega_s}+O(n^{-2}),\] and therefore \[\label{eq:r-theta-reduced} r=\frac{c^2s}{n^2} \left(\frac{r_s}{\Gamma_s}+\frac{t_s}{\Omega_s}\right) +O(n^{-3}).\tag{9}\] Since \[\frac{r_s}{\Gamma_s} =\frac{1-(b+1)\theta_s}{b\theta_s}+O(n^{-1}), \qquad \frac{t_s}{\Omega_s} =\frac{b\theta_s}{1-\theta_s}+O(n^{-1}),\] and \(s=\theta_sn\), 9 yields \[r=\frac{c^2}{n}h_b(\theta_s)+O(n^{-2}).\] Together with \(u_s=n-1-c+cs/n\), this proves 5 . ◻
Specializing these estimates to the two endpoint graphs gives the expansions used later to locate the crossing point.
Corollary 1. Fix \(c_0>b+1\). Then, uniformly for \(c\in[c_0,2b+1]\), \[\label{eq:end-l1} \Lambda_1\left(1-\frac{c}{n}\right) =n-1-(b+1)+\frac{c(b+1)}{(c-b-1)n}+O(n^{-2}).\tag{10}\]
Proof. Apply the fixed-\(s\) part of 4 with \(s=1\). ◻
Corollary 2. Fix \(c_0>b+1\). Then, uniformly for \(c\in[c_0,2b+1]\), \[\label{eq:end-lk} \Lambda_k\left(1-\frac{c}{n}\right) =n-1-\frac{b}{b+1}c +\frac{c(c-\ell-1)}{(b+1)n}+O(n^{-2}),\tag{11}\] where \(\ell=n-(b+1)k-1\).
Proof. Put \[\label{eq:theta-k} \theta_k\mathrel{\vcenter{:}}=\frac{k}{n} =\frac{1}{b+1}-\frac{\ell+1}{(b+1)n}.\tag{12}\] Applying the second part of 4 with \(s=k\) gives \[\Lambda_k\left(1-\frac{c}{n}\right) =n-1-c+\frac{ck}{n} +\frac{c^2}{n}h_b(\theta_k)+O(n^{-2}).\] Since \(h_b(1/(b+1))=1/(b+1)\) and \(\theta_k=1/(b+1)+O(n^{-1})\), the result follows. ◻
4 It is enough to compare the spectral radii of \(G_1\) and \(G_k\)↩︎
In this section, for fixed \(n\), \(b\), and \(\alpha\), we compare the spectral radii of graphs in \(\{G_s\}_{s=1}^k\).
The characteristic polynomial of \(\widetilde{B}_s\) is \[\chi_s(x)\mathrel{\vcenter{:}}=\det(xI-\widetilde{B}_s) =(x-u_s)(x-v_s)(x-w_s) -\beta^2s\left[r_s(x-w_s)+t_s(x-v_s)\right].\] On the interval \(x>\max\{v_s,w_s\}\), we have \[\frac{\chi_s(x)}{(x-v_s)(x-w_s)} =x-u_s-\beta^2s\left(\frac{r_s}{x-v_s} +\frac{t_s}{x-w_s}\right).\] The derivative of the right-hand side with respect to \(x\) is \[1+\beta^2s\left(\frac{r_s}{(x-v_s)^2} +\frac{t_s}{(x-w_s)^2}\right)>0.\] Since \(\Lambda_s>\max\{v_s,w_s\}\) and \(\chi_s(\Lambda_s)=0\) by 7, this quotient is strictly increasing and reaches \(0\) at \(x=\Lambda_s\). Therefore, for every \(x>\max\{v_s,w_s\}\), \[\label{eq:chi-sign-criterion} \chi_s(x)\ge0\quad\Longleftrightarrow\quad x\ge\Lambda_s, \qquad \chi_s(x)>0\quad\Longleftrightarrow\quad x>\Lambda_s.\tag{13}\]
Lemma 9. Let \(\alpha\in(\frac{1}{2},1)\), let \(n\) be even, and let \(b\ge 3\) be odd. Set \(k=\left\lfloor\frac{n-2}{b+1}\right\rfloor\). Then, for fixed \(x\ge u_k\), the function \(s\mapsto\chi_s(x)\) is strictly concave on \([1,k]\).
Proof. Write \[n=(b+1)k+\ell+1,\qquad 1\le \ell\le b.\] Treating \(s\) as a real variable, a direct calculation gives \[\label{eq:chi-second-derivative} \frac{\partial^2 \chi_s(x)}{\partial s^2} =-2\left(b(x-u_k)+\beta H_s\right),\tag{14}\] where \[\label{eq:Hs-definition} H_s\mathrel{\vcenter{:}}= 3b\left((b+2)\beta-1\right)s +b(n+k-1)-2b\beta n+3b\beta+2\beta-1 .\tag{15}\] Since \(x\ge u_k\) and \(\beta>0\), it remains to prove that \(H_s>0\) for \(1\le s\le k\).
The coefficient of \(s\) in \(H_s\) is \(3b((b+2)\beta-1)\). If \(0<\beta\le 1/(b+2)\), then \(H_s\ge H_k\). Moreover \(H_k\) is affine in \(\beta\), and \[H_k\big|_{\beta=0} =b\left((b-1)k+\ell\right)-1>0,\] while \[H_k\big|_{\beta=\frac{1}{b+2}} =\frac{b\left(b^2k+2bk+b\ell+2k\right)}{b+2}>0.\] Thus \(H_s>0\) in this case.
If \(1/(b+2)\le\beta<1/2\), then \(H_s\ge H_1\). Again \(H_1\) is affine in \(\beta\), and \[H_1\big|_{\beta=\frac{1}{b+2}} =\frac{b\left(b^2k+2bk+b\ell+2k\right)}{b+2}>0,\] while \[H_1\big|_{\beta=\frac{1}{2}} =\frac{b(3b+2k+1)}{2}>0.\] Hence \(H_s>0\) also in this case. Therefore \(\partial^2\chi_s(x)/\partial s^2<0\) on \([1,k]\), so \(s\mapsto\chi_s(x)\) is strictly concave. ◻
The next theorem shows that the spectral radius of \(G_s\) is dominated by that of one of the two endpoints, \(G_1\) and \(G_k\).
Theorem 5. Let \(n\) be even and let \(b\ge 3\) be odd. Set \(k=\left\lfloor\frac{n-2}{b+1}\right\rfloor\). Assume \(k\ge 1\). Then for every \(\alpha\in(\frac{1}{2},1)\), \[\max_{1\le s\le k}\rho_{\alpha}(G_s)=\max\{\rho_{\alpha}(G_1),\rho_{\alpha}(G_k)\}.\]
Proof. If \(k\le 2\), the assertion is immediate. Hence assume \(k\ge 3\). Set \[\Lambda_\ast\mathrel{\vcenter{:}}=\max\{\Lambda_1,\Lambda_k\}.\] It suffices to prove that \[\Lambda_\ast>\Lambda_s\qquad (2\le s\le k-1).\]
We first check that \(\Lambda_\ast>\max\{v_s,w_s\}\) for every \(s\). By the Perron–Frobenius argument in 7, \(\Lambda_i>\max\{u_i,v_i,w_i\}\) for \(i=1,k\). Since \(v_s=n-bs-2-\beta s\) is decreasing in \(s\), we have \[v_s\le v_1<\Lambda_1\le \Lambda_\ast \qquad (1\le s\le k).\] Also, \(w_s=\alpha s\) is increasing in \(s\), and \[u_k-w_k =\alpha n-1-(2\alpha-1)k \ge \alpha n-1-(2\alpha-1)\frac{n}{2} =\frac{n}{2}-1>0.\] Hence \[w_s\le w_k<u_k<\Lambda_k\le\Lambda_\ast \qquad (1\le s\le k).\] Thus \[\label{eq:xstar-domain} \Lambda_\ast>\max\{v_s,w_s\} \qquad (1\le s\le k).\tag{16}\]
Moreover, by 13 and the definition of \(\Lambda_\ast\), \[\chi_1(\Lambda_\ast)\ge0, \qquad \chi_k(\Lambda_\ast)\ge0.\] Since \(\Lambda_\ast>u_k\), 9 implies that \(s\mapsto\chi_s(\Lambda_\ast)\) is strictly concave on \([1,k]\). Therefore, for every \(2\le s\le k-1\), \[\chi_s(\Lambda_\ast)> \frac{k-s}{k-1}\chi_1(\Lambda_\ast) +\frac{s-1}{k-1}\chi_k(\Lambda_\ast) \ge0.\] Applying 13 once more gives \[\Lambda_\ast>\Lambda_s \qquad (2\le s\le k-1).\] This completes the proof. ◻
5 The comparison of the spectral radii of \(G_1\) and \(G_k\)↩︎
We now compare the spectral radius of the two endpoint graphs \(G_1\) and \(G_k\). By the last section, this comparison suffices because the graph with the largest spectral radius in the family must be one of these two endpoint graphs. Throughout this section, write \[n=(b+1)k+\ell+1\quad(1\le\ell=r_k\le b), \qquad c=n(1-\alpha).\] Thus \(0<c<n/2\) for \(\alpha\in(\frac{1}{2},1)\). Put \[D_n(c)\mathrel{\vcenter{:}}= \Lambda_1\left(1-\frac{c}{n}\right)-\Lambda_k\left(1-\frac{c}{n}\right).\] We shall prove that, for each fixed \(n\) under consideration, \(D_n(c)\) has exactly one zero. Specifically, we will prove that \(D_n(c)\) is negative on a left interval, strictly increasing through a unique zero on a middle interval, and positive on a right interval. 1 illustrates this behavior.
For the rest of the section, set \[K_b\mathrel{\vcenter{:}}= \max\{2b+3,14\}, \qquad N_b\mathrel{\vcenter{:}}= (b+1)K_b+2.\] Equivalently, \[K_b=\begin{cases} 14, & b\in\{3,5\}, \\ 2b+3, & b\ge 7,\,b\text{ odd}, \end{cases} \qquad N_b=\begin{cases} 58, & b=3, \\ 86, & b=5, \\ 2b^2+5b+5, & b\ge7,\,b\text{ odd}. \end{cases}\] Note that \(n\ge N_b\) is equivalent to \(k\ge K_b\).
Lemma 10. Let \(b\ge3\) be odd and let \(n\ge N_b\) be even. Then \[D_n(c)<0\qquad (0<c\le b+1).\]
Proof. If \(0<c\le b+\frac{1}{2}\), a direct calculation gives \(u_1-v_1\ge\frac{1}{2}\) and \(u_1-w_1\ge\frac{n}{2}\). Writing \(\Lambda_1=u_1+r\) in the Schur equation then gives \[\label{eq:step1-1-1} r= \frac{c^2}{n^2} \left( \frac{r_1}{\Lambda_1-v_1} +\frac{b+1}{\Lambda_1-w_1} \right) \le\frac{2c^2}{n}.\tag{17}\] Here the last inequality follows from \[\frac{r_1}{\Lambda_1-v_1}+\frac{b+1}{\Lambda_1-w_1} \le \frac{n-b-2}{u_1-v_1}+\frac{b+1}{u_1-w_1} \le 2(n-b-2)+2(b+1) =2(n-1)<2n.\] Since \(\Lambda_k>u_k\) and \[\label{eq:step1-1-2} u_k-u_1=\frac{c(k-1)}{n},\tag{18}\] while \(k\ge K_b\), we have \[\label{eq:step1-1-3} \frac{k-1}{n}>\frac{2(b+\frac{1}{2})}{n}.\tag{19}\]
Combining these facts, we have \[u_k-u_1 \overset{\eqref{eq:step1-1-2}}{=} \frac{c(k-1)}{n} \overset{\eqref{eq:step1-1-3}}{>} \frac{2c\left(b+\frac{1}{2}\right)}{n} \ge \frac{2c^2}{n} \overset{\eqref{eq:step1-1-1}}{\ge} r,\] Hence \[\Lambda_1=u_1+r<u_1+(u_k-u_1)=u_k<\Lambda_k,\] therefore \(D_n(c)<0\) for \(0<c\le b+\frac{1}{2}\).
It remains to consider \(b+\frac{1}{2}\le c\le b+1\). Let \(a=c\sqrt{r_1}/n\), \(d=c\sqrt{b+1}/n\), and put \(x=u_1+3/4\).
Since \(r_1=n-(b+1)-1=n-b-2<n\), we have \[\label{eq:step1-2-1} a^2=\frac{c^2r_1}{n^2} \le \frac{(b+1)^2}{n}.\tag{20}\] We also have \[d^2=\frac{c^2(b+1)}{n^2} \le \frac{(b+1)^3}{n^2}.\] Moreover, since \(x-w_1=u_1-w_1+3/4\) and \[u_1-w_1=n-2-c+\frac{2c}{n}\ge n-b-3\ge\frac{n}{2},\] we obtain \[\label{eq:step1-2-2} \frac{d^2}{x-w_1} \le \frac{(b+1)^3/n^2}{n/2} = \frac{2(b+1)^3}{n^3}.\tag{21}\] Finally, using \(x-v_1,x-w_1>x-u_1=3/4\), it holds that \[\label{eq:step1-2-3} \frac{\chi_1(x)}{(x-v_1)(x-w_1)} =x-u_1-\frac{a^2}{x-v_1}-\frac{d^2}{x-w_1} \ge\frac{3}{4}-\frac{4(b+1)^2}{3n} -\frac{2(b+1)^3}{n^3}.\tag{22}\]
We claim that 22 is positive for every \(n\ge N_b\). Indeed, for \(b=3\text{ (resp. }5\text{)}\), this is checked directly from \(n\ge58\text{ (resp. }86\text{)}\). For \(b\ge7\), the lower bound is at least \[\frac{3}{4}-\frac{4(b+1)^2}{3(2b^2+5b+5)} -\frac{2(b+1)^3}{(2b^2+5b+5)^3}>0,\] since, after multiplying both sides by \(12(2b^2+5b+5)^3\), the numerator is \[8b^6+92b^5+466b^4+1241b^3+1933b^2+1703b+701,\] whose coefficients are all positive. Therefore \(x=u_1+3/4>\Lambda_1\).
On the other hand, \[u_k-u_1 =\frac{c(k-1)}{n} \overset{n\le(b+1)(k+1)}{\ge} \frac{(b+\frac{1}{2})(K_b-1)}{(b+1)(K_b+1)} >\frac{3}{4}.\] The last inequality is immediate for \(b=3,5\), where \(K_b=14\), and for \(b\ge7\) it becomes \[\frac{(b+\frac{1}{2})(2b+2)}{(b+1)(2b+4)} =\frac{2b+1}{2b+4}>\frac{3}{4}.\] Thus \(\Lambda_k>u_k>u_1+3/4=x>\Lambda_1\) and therefore \(D_n(c)<0\), completing the proof. ◻
Lemma 11. Let \(b\ge3\) be odd and let \(n\ge N_b\) be even. Then \(D_n\) is strictly increasing on \([b+1,2b+1]\).
Proof. Consider the quotient matrices \(\widetilde{B}_s(c)\). For a unit Perron vector \(z_s=(p_s,q_s,\zeta_s)^\mathrm{T}\) of \(\widetilde{B}_s(c)\), differentiating the matrix \(\widetilde{B}_s(c)\) with respect to \(c\) gives \[\label{eq:step2-1-1} \Lambda_s'(c) =z_s^\mathrm{T}\widetilde{B}_s'(c)z_s =\left(-1+\frac{s}{n}\right)p_s^2 -\frac{s}{n}q_s^2 -\frac{s}{n}\zeta_s^2 +\frac{2\sqrt{s r_s}}{n}p_sq_s +\frac{2\sqrt{s t_s}}{n}p_s\zeta_s.\tag{23}\] We claim that \[\Lambda_1'(c)>-\frac{2}{3}, \qquad \Lambda_k'(c)<-\frac{2}{3} \qquad (b+1\le c\le2b+1).\]
First consider \(s=1\). Let \(a=c\sqrt{r_1}/n\), \(d=c\sqrt{b+1}/n\), and \(\gamma=\sqrt{3/2}\). Put \(x=v_1+\gamma a\). We claim that \[x-u_1-\frac{a^2}{x-v_1}-\frac{d^2}{x-w_1} =v_1-u_1+\left(\gamma-\frac{1}{\gamma}\right)a -\frac{d^2}{x-w_1}>0\] for all \(n\ge N_b\).
From \[\begin{align} v_1-u_1&=c-b-1-\frac{2c}{n}\ge-\frac{2c}{n}, \\ \left(\gamma-\frac{1}{\gamma}\right)a&=\frac{1}{\sqrt6}\cdot\frac{c\sqrt{r_1}}{n} \ge\frac{1}{\sqrt6}\cdot\frac{c\sqrt{n/2}}{n}=\frac{c}{\sqrt{12n}}, \\ \frac{d^2}{x-w_1}&=\frac{c^2(b+1)/n^2}{x-w_1} \le\frac{(2b+1)^2(b+1)/n^2}{n/2}=\frac{2(2b+1)^2(b+1)}{n^3}, \end{align}\] we have \[v_1-u_1+\left(\gamma-\frac{1}{\gamma}\right)a -\frac{d^2}{x-w_1} \ge c\left(\frac{1}{\sqrt{12n}}-\frac{2}{n}\right) -\frac{2(2b+1)^2(b+1)}{n^3}.\] We prove that the right-hand side of the above is positive. Since \(n\ge58\) and \(c\ge b+1\), we have \[\begin{align} c\left(\frac{1}{\sqrt{12n}}-\frac{2}{n}\right) -\frac{2(2b+1)^2(b+1)}{n^3} &\ge\frac{b+1}{40\sqrt n} -\frac{2(2b+1)^2(b+1)}{n^3} \\ &=(b+1)\left(\frac{1}{40\sqrt n}-\frac{2(2b+1)^2}{n^3}\right)>0. \end{align}\] The last inequality follows from \(n^{5/2}>80(2b+1)^2\), which is immediate from \(n\ge N_b\). Hence \(\Lambda_1\le v_1+\gamma a\). Therefore the Perron equation gives \[\label{eq:step2-1-2} \begin{bmatrix} u_1 & a & d\\ a & v_1 & 0\\ d & 0 & w_1 \end{bmatrix} \begin{bmatrix} p_1 \\ q_1 \\ \zeta_1 \end{bmatrix} =\Lambda_1 \begin{bmatrix} p_1 \\ q_1 \\ \zeta_1 \end{bmatrix} \implies a p_1+v_1q_1=\Lambda_1 q_1 \implies \frac{q_1}{p_1}=\frac{a}{\Lambda_1-v_1}\ge\frac{1}{\gamma},\tag{24}\] and therefore \(p_1^2\le\gamma^2/(1+\gamma^2)=3/5\) since \(p_1^2+q_1^2\le 1\). Dropping the positive off-diagonal terms of 23 gives \[\Lambda_1'(c) \ge\left(-1+\frac{1}{n}\right)p_1^2-\frac{1}{n}(1-p_1^2) =\left(-1+\frac{2}{n}\right)p_1^2-\frac{1}{n} >-\frac{2}{3}.\]
Now consider \(s=k\). Let \(A=c\sqrt{k\ell}/n\) and \(E=c\sqrt{k(bk+1)}/n\). Since \(\Lambda_k>u_k\), as in 24 , the Perron equations give \[\frac{q_k}{p_k}\le \frac{A}{u_k-v_k}, \qquad \frac{\zeta_k}{p_k}\le \frac{E}{u_k-w_k}.\] Moreover, on \(b+1\le c\le2b+1\), \[u_k-v_k\ge bk-2b,\qquad u_k-w_k\ge bk-2b .\] Substituting these into 23 and dropping the negative terms yields \[\Lambda_k'(c) \le -1+\frac{k}{n} + \frac{2c k(\ell+bk+1)}{n^2(bk-2b)} .\] Since \(k\ge K_b\), \(\ell\le b\), \(c\le2b+1\), and \(n\ge(b+1)k\), the last positive term \[\frac{2(2b+1)(b+bk+1)}{(b+1)^2kb(k-2)} \le \frac{1}{12}.\] For \(b=3,5\) this is verified by substituting \(k\ge K_b=14\). For \(b\ge7\), this is decreasing in \(k\), so it is enough to check \(k=2b+3\). After clearing denominators this is equivalent to \[4b^5+16b^4-73b^3-226b^2-141b-24>0,\] which holds since the maximum real root of this polynomial is approximately \(4.16\). Therefore \[\Lambda_k'(c) \le-\frac{b}{b+1}+\frac{1}{12} \le-\frac{2}{3}.\] Thus \(D_n'(c)=\Lambda_1'(c)-\Lambda_k'(c)>0\) throughout the interval, completing the proof. ◻
Lemma 12. Let \(b\ge3\) be odd and let \(n\ge N_b\) be even. Then \[D_n(c)>0\qquad (2b+1\le c<n/2).\]
Proof. For \(c\ge 2b+1\), \(v_1>\max\{u_1,w_1\}\). Thus \[\Lambda_1>v_1=n-b-2-\frac{c}{n}.\] On the other hand, by 8, \[\Lambda_k \le u_k+\frac{c^2k}{n^2} \left(\frac{\ell}{u_k-v_k}+\frac{bk+1}{u_k-w_k}\right).\] This is valid because \(c<n/2\) and \(n>2k\) gives \[\begin{align} u_k-v_k &=bk+1-c\left(1-\frac{2k}{n}\right) >\frac{(b+1)k+1-\ell}{2}>0, \\ u_k-w_k &=n-k-1-c\left(1-\frac{2k}{n}\right) >\frac{(b+1)k+\ell-1}{2}>0. \end{align}\] Consequently, since \(1\le\ell\le b<k+1\), it holds that \[\begin{align} u_k-v_k&>\frac{(b+1)k+1-\ell}{2} \ge\frac{(b+1)k+1-b}{2} =\frac{bk+(k+1-b)}{2} >\frac{bk}{2}, \\ u_k-w_k&>\frac{(b+1)k}{2}. \end{align}\] Therefore \[\frac{k}{n^2}\left(\frac{\ell}{u_k-v_k}+\frac{bk+1}{u_k-w_k}\right) < \frac{1}{n^2}\left(\frac{2\ell}{b}+\frac{2(bk+1)}{b+1}\right) \le \frac{1}{n^2} \left(2+\frac{2(bk+1)}{b+1}\right) \le \frac{3b}{(b+1)^2n},\] where the last inequality follows from \(n\ge (b+1)k+2\) and \(b(b+1)k\ge2b^2+4\), the latter being immediate from \(b\ge3\) and \(k\ge3\). Hence \[D_n(c)=\Lambda_1-\Lambda_k >\left(n-b-2-\frac{c}{n}\right)-\left(u_k+\frac{3bc^2}{(b+1)^2n}\right) =-b-1+c\left(1-\frac{k+1}{n}\right)-\frac{3bc^2}{(b+1)^2n}.\]
Since \[1-\frac{k+1}{n} =\frac{b}{b+1}-\frac{b-\ell}{(b+1)n} \ge\frac{b}{b+1}-\frac{b}{(b+1)n},\] we get \[D_n(c) \ge-b-1+c\left(\frac{b}{b+1}-\frac{b}{(b+1)n}\right) -\frac{3bc^2}{(b+1)^2n} \eqqcolon Q_n(c).\] Notice that \(Q_n(c)\) is a concave quadratic function of \(c\), so on \(2b+1\le c\le n/2\) its minimum is attained at an endpoint. We claim that at \(c=2b+1\) it is \[Q_n(2b+1)=\frac{b^2-b-1}{b+1} -\frac{b(2b+1)}{(b+1)n} -\frac{3b(2b+1)^2}{(b+1)^2n}>0,\] and at \(c=n/2\) it equals \[Q_n(n/2)=\frac{bn(2b-1)}{4(b+1)^2} -\frac{b}{2(b+1)}-b-1>0.\] Indeed, the first of these inequalities follows from \[\frac{b^2-b-1}{b+1} >\frac{b(2b+1)}{(b+1)n}+\frac{3b(2b+1)^2}{(b+1)^2n},\] which is immediate for \(b=3,5\) after substituting \(N_b=58,86\). For \(b\ge 7\), after substituting \(N_b=2b^2+5b+5\) and multiplying both sides by \((b+1)^2(2b^2+5b+5)\), this is equivalent to \[2b^5+5b^4-13b^3-27b^2-19b-5,\] which is positive for all \(b\ge 7\) since the maximum real root of this polynomial is approximately \(2.60\). The second follows from \[\frac{bn(2b-1)}{4(b+1)^2} >b+1+\frac{b}{2(b+1)},\] again using \(n\ge N_b\). This is immediate for \(b=3,5\) after substituting \(N_b=58,86\). For \(b\ge7\), after substituting \(N_b=2b^2+5b+5\) and multiplying both sides by \(4(b+1)^2\), this is equivalent to \[4b^4+4b^3-9b^2-19b-4>0,\] which is positive for all \(b\ge 7\) since the maximum real root of this polynomial is approximately \(1.82\). Thus \(D_n(c)>0\) on the asserted interval, completing the proof. ◻
Now that the three lemmas are settled, we can derive the main result of this section.
Theorem 6. Fix an odd integer \(b\ge3\) and set \[N_b=(b+1)\max\{2b+3,14\}+2 .\] For every even \(n\ge N_b\), there exists a unique \(\alpha_\ast(n,b)\in(\frac{1}{2},1)\) such that \[\Lambda_1(\alpha_\ast)=\Lambda_k(\alpha_\ast).\] Consequently, \[\begin{align} \Lambda_1(\alpha)>\Lambda_k(\alpha) &\quad\Longleftrightarrow\quad \frac{1}{2}<\alpha<\alpha_\ast(n,b), \\ \Lambda_k(\alpha)>\Lambda_1(\alpha) &\quad\Longleftrightarrow\quad \alpha_\ast(n,b)<\alpha<1, \\ \Lambda_1(\alpha)=\Lambda_k(\alpha) &\quad\Longleftrightarrow\quad \alpha=\alpha_\ast(n,b). \end{align}\] Moreover, \[\alpha_\ast(n,b) =1-\frac{(b+1)^2}{bn} +\frac{(b+1)^2(b^3+b\ell-b-1)}{b^3n^2} +O(n^{-3}).\]
Proof. By 10, \(D_n(b+1)<0\), while by 12, \(D_n(2b+1)>0\). Since \(D_n\) is strictly increasing on \([b+1,2b+1]\) by 11, it has exactly one zero \(c_\ast\in(b+1,2b+1)\). The same two endpoint lemmas exclude all zeros outside this interval. Hence \(\alpha_\ast=1-c_\ast/n\in(\frac{1}{2},1)\) is the unique crossing point.
It remains to locate the zero. The endpoint expansions [cor:Lambda-1-expansion,cor:Lambda-k-expansion] give, uniformly on compact subintervals of \((b+1,2b+1)\), \[\label{eq:Dn-FG-expansion} D_n(c)=F(c)+\frac{1}{n}G(c)+O(n^{-2}),\tag{25}\] where \[F(c)\mathrel{\vcenter{:}}=\frac{bc}{b+1}-(b+1), \qquad G(c)\mathrel{\vcenter{:}}= \frac{c(b+1)}{c-b-1}-\frac{c(c-\ell-1)}{b+1}.\] The leading term \(F(c)\) has the unique zero \[c_0\mathrel{\vcenter{:}}=\frac{(b+1)^2}{b}.\] Since \(b+1<c_0<2b+1\), we may fix small \(\delta>0\) such that \(b+1<c_0-\delta<c_0+\delta<2b+1\). From 25 , or just its leading part, \[D_n(c)=F(c)+O(n^{-1})\] uniformly on \([c_0-\delta,c_0+\delta]\). Hence \(D_n(c_0-\delta)<0<D_n(c_0+\delta)\) for all sufficiently large \(n\). Since the zero is unique, \(c_\ast\in(c_0-\delta,c_0+\delta)\).
We now refine this location by one Taylor step. Write \[c_\ast=c_0+\frac{a}{n}+O(n^{-2}).\] Substituting this into 25 and using \(F(c_0)=0\) gives \[0=D_n(c_\ast) =\frac{1}{n}\left(aF'(c_0)+G(c_0)\right)+O(n^{-2}).\] Therefore \[a=-\frac{G(c_0)}{F'(c_0)} =-\frac{(b+1)^2(b^3+b\ell-b-1)}{b^3}.\] Thus \[c_\ast =\frac{(b+1)^2}{b} -\frac{(b+1)^2(b^3+b\ell-b-1)}{b^3n} +O(n^{-2}).\] The stated expansion for \(\alpha_\ast=1-c_\ast/n\) follows. Finally \(c=n(1-\alpha)\) is strictly decreasing in \(\alpha\), so the two sign alternatives are exactly as claimed. ◻
6 Proofs of the main theorems in the Introduction↩︎
We are now ready to prove the theorems stated in the Introduction, which completes the paper.
Proof of 2. The existence, uniqueness, sign alternatives, and the expression for the crossing of \(\Lambda_1\) and \(\Lambda_k\) are exactly 6. Combining these with the endpoint reduction in 5 gives the asserted extremal graphs in the whole family \(\{G_s\}_{s=1}^k\). ◻
Proof of 3. Suppose that \(G\) has no odd \([1,b]\)-factor. By 4, if \[\rho_{\alpha}(G)\ge\max_{1\le s\le k}\rho_{\alpha}(G_s),\] then \(G\cong G_s\) for some graph \(G_s\) that is extremal in the family. The extremal graphs are identified in 2: for \(\frac{1}{2}<\alpha<\alpha_\ast(n,b)\) it is \(G\cong G_1\); for \(\alpha_\ast(n,b)<\alpha<1\) it is \(G\cong G_k\); and for \(\alpha=\alpha_\ast(n,b)\) the extremal graphs are \(G\cong G_1\) and \(G\cong G_k\). This is precisely the conclusion of 3. ◻