Introduction
All graphs considered here are finite, simple, and undirected. Let G G G be a graph with vertex set V ( G ) = { 1 , 2 , … , n } V(G)=\{1,2,\ldots,n\} V ( G ) = { 1 , 2 , … , n } and edge set E ( G ) E(G) E ( G ) , ∣ E ( G ) ∣ = m |E(G)|=m ∣ E ( G ) ∣ = m . If two vertices i i i and j j j are adjacent, we write i ∼ j i\sim j i ∼ j and denote the corresponding edge by { i , j } \{i,j\} { i , j } . The adjacency matrix of G G G is A ( G ) = [ a i j ] A(G)=[a_{ij}] A ( G ) = [ a ij ] , where a i j = 1 a_{ij}=1 a ij = 1 if i ∼ j i\sim j i ∼ j and a i j = 0 a_{ij}=0 a ij = 0 otherwise. Since A ( G ) A(G) A ( G ) is real and symmetric, its eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n \mu_1\geq\mu_2\geq\cdots\geq\mu_n μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n are real; the largest one, μ 1 ( G ) \mu_1(G) μ 1 ( G ) , is the spectral radius of G G G and is denoted by ρ ( G ) \rho(G) ρ ( G ) .
For i ∈ V ( G ) i\in V(G) i ∈ V ( G ) let N G ( i ) N_G(i) N G ( i ) be the neighbourhood of i i i , N G [ i ] = N G ( i ) ∪ { i } N_G[i]=N_G(i)\cup\{i\} N G [ i ] = N G ( i ) ∪ { i } its closed neighbourhood and d ( i ) = ∣ N G ( i ) ∣ d(i)=|N_G(i)| d ( i ) = ∣ N G ( i ) ∣ its degree. Following the standard terminology of chemical graph theory, the neighbourhood degree sum of i i i is
δ ( i ) = ∑ j ∼ i d ( j ) . \delta(i)=\sum_{j\sim i}d(j). δ ( i ) = j ∼ i ∑ d ( j ) .
We write δ max = δ max ( G ) = max { δ ( i ) : i ∈ V ( G ) } \delta_{\max}=\delta_{\max}(G)=\max\{\delta(i):i\in V(G)\} δ m a x = δ m a x ( G ) = max { δ ( i ) : i ∈ V ( G )} and δ min = δ min ( G ) = min { δ ( i ) : i ∈ V ( G ) } \delta_{\min}=\delta_{\min}(G)=\min\{\delta(i):i\in V(G)\} δ m i n = δ m i n ( G ) = min { δ ( i ) : i ∈ V ( G )} , and similarly d max , d min d_{\max},d_{\min} d m a x , d m i n for the maximum and minimum degree. Clearly
d min 2 ≤ δ min ≤ δ max ≤ d max 2 . (1) d_{\min}^{2}\leq\delta_{\min}\leq\delta_{\max}\leq d_{\max}^{2}. \tag*{(1)} d m i n 2 ≤ δ m i n ≤ δ m a x ≤ d m a x 2 . (1)
Degree-based graph invariants such as the first and second Zagreb indices [14 , 15 ] and the forgotten index [10 ] have been studied intensively, and in recent years their neighbourhood versions, in which d ( i ) d(i) d ( i ) is replaced by δ ( i ) \delta(i) δ ( i ) , have attracted considerable attention [25 , 26 ] . Ghorbani and Hosseinzadeh [11 ] introduced the neighbourhood first and second Zagreb indices
M 1 ′ ( G ) = ∑ { i , j } ∈ E ( G ) ( δ ( i ) + δ ( j ) ) , M 2 ′ ( G ) = ∑ { i , j } ∈ E ( G ) δ ( i ) δ ( j ) . M'_1(G)=\sum_{\{i,j\}\in E(G)}(\delta(i)+\delta(j)), \qquad M'_2(G)=\sum_{\{i,j\}\in E(G)}\delta(i)\delta(j). M 1 ′ ( G ) = { i , j } ∈ E ( G ) ∑ ( δ ( i ) + δ ( j )) , M 2 ′ ( G ) = { i , j } ∈ E ( G ) ∑ δ ( i ) δ ( j ) .
The index M 2 ′ M'_2 M 2 ′ also appears as M 2 ∗ M^*_2 M 2 ∗ [25 ] and as N M 2 NM_2 N M 2 in the literature. Note that M N ( G ) = ∑ v δ ( v ) 2 M_N(G)=\sum_v\delta(v)^2 M N ( G ) = ∑ v δ ( v ) 2 of [25 , 26 ] differs from M N ′ ( G ) = ∑ v d ( v ) δ ( v ) M'_N(G)=\sum_v d(v)\delta(v) M N ′ ( G ) = ∑ v d ( v ) δ ( v ) . We use the index M 2 ′ M'_2 M 2 ′ in Theorem 7.2 .
In parallel, matrices whose nonzero entries are degree-based edge weights have been introduced in order to study such invariants by spectral methods. Given a symmetric bivariate function F F F , the associated weighted adjacency matrix A F ( G ) A_F(G) A F ( G ) has ( i , j ) (i,j) ( i , j ) -th entry F ( d ( i ) , d ( j ) ) F(d(i),d(j)) F ( d ( i ) , d ( j )) if i ∼ j i\sim j i ∼ j and 0 0 0 otherwise [8 ] ; the extremal theory of ρ ( A F ) \rho(A_F) ρ ( A F ) over trees and unicyclic graphs has been developed by Li and Wang [22 ] and by Zheng, Guan and Jin [32 ] under monotonicity and convexity hypotheses on F F F . Jafari Rad, Jahanbani and Gutman [19 ] considered in particular the first and second Zagreb matrices, whose ( i , j ) (i,j) ( i , j ) -th entries are d ( i ) + d ( j ) d(i)+d(j) d ( i ) + d ( j ) and d ( i ) d ( j ) d(i)d(j) d ( i ) d ( j ) on the edges of G G G ; Mondal et al. [24 ] replaced d ( i ) d(i) d ( i ) by δ ( i ) \delta(i) δ ( i ) in the additive case, studied the energy of the resulting neighbourhood first Zagreb matrix Υ ( G ) = [ δ ( i ) + δ ( j ) ] \Upsilon(G)=[\delta(i)+\delta(j)] Υ ( G ) = [ δ ( i ) + δ ( j )] and established its value as a molecular descriptor. The multiplicative counterpart, which is the matrix considered in the present paper, was introduced by Barik and Verma [1 ] .
Definition 1.1 ([1 ] ). The neighbourhood second Zagreb matrix of a graph G G G , denoted by N F ( G ) N_F(G) N F ( G ) (or simply N F N_F N F ), is the n × n n\times n n × n matrix N F ( G ) = [ n i j ] N_F(G)=[n_{ij}] N F ( G ) = [ n ij ] defined by
n i j = { δ ( i ) δ ( j ) , if i ∼ j in G , 0 , otherwise . n_{ij}=
\begin{cases}
\delta(i)\delta(j), & \text{if } i\sim j \text{ in }G,\\
0, & \text{otherwise}.
\end{cases} n ij = { δ ( i ) δ ( j ) , 0 , if i ∼ j in G , otherwise .
The matrix N F ( G ) N_F(G) N F ( G ) is real and symmetric; its eigenvalues are denoted by λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n , and λ 1 \lambda_1 λ 1 is called the neighbourhood second Zagreb spectral radius of G G G , written ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) . Note that the sum of the entries of N F ( G ) N_F(G) N F ( G ) above the diagonal is precisely M 2 ′ ( G ) M'_2(G) M 2 ′ ( G ) , so that N F ( G ) N_F(G) N F ( G ) is to the neighbourhood second Zagreb index what the adjacency matrix is to the number of edges.
Two reasons make the spectral radius of such a matrix worth bounding. The first is internal to spectral graph theory: for a nonnegative symmetric matrix the spectral radius governs the growth of the entries of its powers, and hence the behaviour of weighted walk counts; it is also the quantity that controls the epidemic threshold in the standard susceptible–infected–susceptible model on a network, where the critical infection rate is the reciprocal of the spectral radius of the underlying weighted adjacency matrix [31 ] . Passing from A ( G ) A(G) A ( G ) to N F ( G ) N_F(G) N F ( G ) amounts to weighting each contact by the product of the neighbourhood degrees of its endpoints, so that ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) measures propagation in a network in which the transmissibility of a contact grows with the connectivity of the surroundings of both of its ends. The second reason is that ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) bounds the neighbourhood second Zagreb energy from both sides, as Theorems 7.2 , 7.4 and 7.6 show, and the energy of the neighbourhood first Zagreb matrix was shown in [24 ] , by a regression analysis of physico-chemical properties, to be a useful molecular descriptor. Every sharpening of a bound on ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) therefore tightens the range within which such a descriptor can lie. We do not undertake a correlation study here; the QSPR analysis of N F N_F N F -based descriptors, in the manner of [24 ] , would be a natural complement to the present work.
In [1 ] , sharp bounds for ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) and for the neighbourhood second Zagreb energy were obtained, together with the corresponding extremal graphs. Our aim here is twofold. First, we sharpen several of the estimates available for ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) . Lemma 3.17 replaces the factor δ max 2 \delta_{\max}^2 δ m a x 2 in the classical comparison ρ N F ( G ) ≤ δ max 2 ρ ( G ) \rho_{N_F}(G)\le\delta_{\max}^2\rho(G) ρ N F ( G ) ≤ δ m a x 2 ρ ( G ) by the largest edge weight W ( G ) = max { i , j } ∈ E ( G ) δ ( i ) δ ( j ) W(G)=\max_{\{i,j\}\in E(G)}\delta(i)\delta(j) W ( G ) = max { i , j } ∈ E ( G ) δ ( i ) δ ( j ) . Theorem 3.6 proves that ρ N F ( G ) ≥ ρ ( G ) 5 \rho_{N_F}(G)\ge\rho(G)^5 ρ N F ( G ) ≥ ρ ( G ) 5 , which is never weaker than the lower estimate δ min 2 ρ ( G ) \delta_{\min}^2\rho(G) δ m i n 2 ρ ( G ) , and strictly better unless G G G is regular or bipartite semiregular.
Also this is the key to the equality case of the Berman-Zhang-type bound of Theorem 3.8. Lemma 3.1 allows the equality conditions in Theorem 3.10 and Corollary 3.12 to be stated as characterisations rather than as sufficient conditions; the same argument sharpens the corresponding statements for the matrix Υ ( G ) \Upsilon(G) Υ ( G ) of [24 ] , see Remarks 3.11 and 3.16. Secondly, we determine bounds for classes of graphs that have not been considered from this point of view, most notably the unicyclic graphs, for which we show that the cycle C n C_n C n is the unique minimiser of ρ N F \rho_{NF} ρ N F on U n \mathcal{U}_n U n and that the triangle with n − 3 n-3 n − 3 pendant edges attached at one vertex is the unique maximiser.
Contributions and relation to earlier work
Since several of the estimates below are of a kind that has already been considered for N F ( G ) N_F(G) N F ( G ) in [1 ] , for the additive matrix Υ ( G ) \Upsilon(G) Υ ( G ) in [2 , 24 ] , or for the adjacency matrix itself, we state result by result what the present paper contributes. Table 1 summarises this.
Table 1. What is new in this paper? The classical results used as tools are Lemma 3.2 [9 ] , Lemma 6.2 [16 ] , Hong’s inequality [17 ] , Nikiforov’s inequality [27 , 28 ] , Kober’s inequality [20 ] , and the theorems of Smith [30 ] and of Cheng and Liu [6 ] .
The paper is organised as follows. § 2 collects the matrix tools that will be used and records the value of ρ N F \rho_{NF} ρ N F for several basic families of graphs. § 3 contains bounds valid for all connected graphs; in particular Theorem 3.6 gives the lower bound ρ N F ( G ) ≥ ρ ( G ) 5 \rho_{NF}(G) \ge\rho(G)^5 ρ N F ( G ) ≥ ρ ( G ) 5 , Theorem 3.8 gives a Berman–Zhang-type upper bound whose extremal graphs are exactly the regular and bipartite semiregular graphs, and Lemma 3.17 improves the classical estimate ρ N F ( G ) ≤ δ max 2 ρ ( G ) \rho_{NF}(G) \le\delta_{\max}^{2}\rho(G) ρ N F ( G ) ≤ δ m a x 2 ρ ( G ) by replacing δ max 2 \delta_{\max}^{2} δ m a x 2 with the largest edge weight of N F ( G ) N_F(G) N F ( G ) . § 4 treats bipartite graphs and trees, and § 5 is devoted to unicyclic graphs, where a two-sided bound with both extremal cases discussed is obtained. Section 6 relates ρ N F ( G ) \rho_{NF}(G) ρ N F ( G ) to the first Zagreb index and Section 7 contains bounds for the neighbourhood second Zagreb energy.
Preliminaries
We use the following standard facts; see [18 Chapters 1, 4 and 8] and [7 ] .
Lemma 2.1 (Rayleigh–Ritz [18 ] ). Let M M M be a real symmetric n × n n \times n n × n matrix with the largest eigenvalue λ max ( M ) \lambda_{\max}(M) λ m a x ( M ) . Then λ max ( M ) = max ∥ x ∥ = 1 x T M x \lambda_{\max}(M) = \max_{\lVert x\rVert=1} x^{T}Mx λ m a x ( M ) = max ∥ x ∥ = 1 x T M x , and x T M x ≤ λ max ( M ) x^{T}Mx \le\lambda_{\max}(M) x T M x ≤ λ m a x ( M ) for every unit vector x x x , with equality if and only if x x x is an eigenvector of M M M associated with λ max ( M ) \lambda_{\max}(M) λ m a x ( M ) .
Lemma 2.2 (Perron–Frobenius [18 ] ). Let B = [ b i j ] B = [b_{ij}] B = [ b ij ] and C = [ c i j ] C = [c_{ij}] C = [ c ij ] be nonnegative n × n n \times n n × n matrices.
(a) If b i j ≤ c i j b_{ij} \le c_{ij} b ij ≤ c ij for all i , j i,j i , j and C C C is irreducible, then ρ ( B ) ≤ ρ ( C ) \rho(B) \le\rho(C) ρ ( B ) ≤ ρ ( C ) , with equality if and only if B = C B = C B = C .
(b) If C C C is irreducible with row sums R 1 , … , R n R_1,\ldots,R_n R 1 , … , R n , then min i R i ≤ ρ ( C ) ≤ max i R i \min_i R_i \le\rho(C) \le\max_i R_i min i R i ≤ ρ ( C ) ≤ max i R i , and either equality holds if and only if R 1 = ⋯ = R n R_1 = \cdots= R_n R 1 = ⋯ = R n .
(c) (Collatz–Wielandt) If C C C is irreducible and z ∈ R n z \in\mathbb{R}^n z ∈ R n is a positive vector, then ρ ( C ) ≤ max i ( C z ) i / z i \rho(C) \le\max_i (Cz)_i/z_i ρ ( C ) ≤ max i ( C z ) i / z i .
Lemma 2.3 (Cauchy interlacing [18 ] ). If M M M is a real symmetric n × n n \times n n × n matrix and M ′ M' M ′ is a principal submatrix of M M M , then λ max ( M ′ ) ≤ λ max ( M ) \lambda_{\max}(M') \le\lambda_{\max}(M) λ m a x ( M ′ ) ≤ λ m a x ( M ) .
If G G G is connected and n ≥ 2 n \ge2 n ≥ 2 , then A ( G ) A(G) A ( G ) is irreducible and all the weights δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) , { i , j } ∈ E ( G ) \{i,j\} \in E(G) { i , j } ∈ E ( G ) , are positive; hence N F ( G ) N_F(G) N F ( G ) is a nonnegative irreducible matrix and ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) is a simple eigenvalue admitting a positive eigenvector, the Perron vector of N F ( G ) N_F(G) N F ( G ) . The next observation, although elementary, explains the structure of N F ( G ) N_F(G) N F ( G ) and will be used repeatedly.
Proposition 2.4. Let G G G be a graph with no isolated vertices and let D δ = diag ( δ ( 1 ) , … , δ ( n ) ) D_\delta= \operatorname{diag}(\delta(1),\ldots,\delta(n)) D δ = diag ( δ ( 1 ) , … , δ ( n )) . Then
N F ( G ) = D δ A ( G ) D δ , N_F(G) = D_\delta A(G)D_\delta, N F ( G ) = D δ A ( G ) D δ , and consequently ρ N F ( G ) = ρ ( A ( G ) D δ 2 ) \rho_{N_F}(G) = \rho(A(G)D_\delta^2) ρ N F ( G ) = ρ ( A ( G ) D δ 2 ) . In particular, if δ ( i ) = c \delta(i) = c δ ( i ) = c for every i ∈ V ( G ) i \in V(G) i ∈ V ( G ) , then N F ( G ) = c 2 A ( G ) N_F(G) = c^2A(G) N F ( G ) = c 2 A ( G ) and ρ N F ( G ) = c 2 ρ ( G ) \rho_{N_F}(G) = c^2\rho(G) ρ N F ( G ) = c 2 ρ ( G ) .
Proof. The ( i , j ) (i,j) ( i , j ) -th entry of D δ A ( G ) D δ D_\delta A(G)D_\delta D δ A ( G ) D δ equals δ ( i ) a i j δ ( j ) \delta(i)a_{ij}\delta(j) δ ( i ) a ij δ ( j ) , which is δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) if i ∼ j i \sim j i ∼ j and 0 otherwise. The matrices D δ A ( G ) D δ D_\delta A(G)D_\delta D δ A ( G ) D δ and A ( G ) D δ 2 A(G)D_\delta^2 A ( G ) D δ 2 are similar via D δ D_\delta D δ , which is invertible because δ ( i ) > 0 \delta(i) > 0 δ ( i ) > 0 for every i i i when G G G has no isolated vertex.
The factorisation in Proposition 2.4 is a congruence, and this has consequences that are not available for the additive matrix Υ ( G ) = [ δ ( i ) + δ ( j ) ] \Upsilon(G) = [\delta(i) + \delta(j)] Υ ( G ) = [ δ ( i ) + δ ( j )] of [24 ] .
Proposition 2.5. Let G G G be a graph with no isolated vertices. Then N F ( G ) N_F(G) N F ( G ) and A ( G ) A(G) A ( G ) are congruent; consequently they have the same inertia, that is, the same number of positive, negative and zero eigenvalues. In particular
rank N F ( G ) = rank A ( G ) and det N F ( G ) = ( ∏ i = 1 n δ ( i ) ) 2 det A ( G ) . \operatorname{rank} N_F(G) = \operatorname{rank} A(G)
\qquad\text{and}\qquad
\det N_F(G) = \left(\prod_{i=1}^{n}\delta(i)\right)^2 \det A(G). rank N F ( G ) = rank A ( G ) and det N F ( G ) = ( i = 1 ∏ n δ ( i ) ) 2 det A ( G ) .
Proof. Since G G G has no isolated vertex, δ ( i ) > 0 \delta(i) > 0 δ ( i ) > 0 for every i i i , so D δ D_\delta D δ is nonsingular and N F ( G ) = D δ A ( G ) D δ N_F(G) = D_\delta A(G)D_\delta N F ( G ) = D δ A ( G ) D δ exhibits a congruence between N F ( G ) N_F(G) N F ( G ) and A ( G ) A(G) A ( G ) . Sylvester’s law of inertia [18 ] gives the equality of inertias, and hence of ranks. The determinant formula follows from det N F ( G ) = ( det D δ ) 2 det A ( G ) \det N_F(G) = (\det D_\delta)^2 \det A(G) det N F ( G ) = ( det D δ ) 2 det A ( G ) .
Proposition 2.5 is a transfer principle: every statement about the inertia of A ( G ) A(G) A ( G ) holds verbatim for N F ( G ) N_F(G) N F ( G ) . We record the consequences used later. Note that each of them would require a separate argument for the additive matrix Υ ( G ) \Upsilon(G) Υ ( G ) , for which no analogue of Proposition 2.4 is available.
Corollary 2.6 (part (iv): [1 Prop. 1(i)] ). Let G G G be a graph on n n n vertices with no isolated vertices. Then
(i) the nullity of N F ( G ) N_F(G) N F ( G ) equals the nullity of G G G ; in particular N F ( G ) N_F(G) N F ( G ) is nonsingular if and only if A ( G ) A(G) A ( G ) is;
(ii) rank N F ( G ) = 2 \operatorname{rank} N_F(G)=2 rank N F ( G ) = 2 if and only if G ≅ K p , q G\cong K_{p,q} G ≅ K p , q for some p , q ≥ 1 p,q\ge1 p , q ≥ 1 ;
(iii) N F ( G ) N_F(G) N F ( G ) has exactly one positive eigenvalue if and only if G G G is a complete multipartite graph;
(iv) if G G G is bipartite, then the spectrum of N F ( G ) N_F(G) N F ( G ) is symmetric about the origin.
Proof. Parts (i)--(iii) follow from Proposition 2.5 together with, respectively, the definition of nullity, the theorem of Cheng and Liu [6 ] describing the graphs of nullity n − 2 n-2 n − 2 (these are the complete bipartite graphs together with isolated vertices, and there are no isolated vertices here), and the theorem of Smith [30 ] characterising the graphs with exactly one positive adjacency eigenvalue. For (iv), let ( X , Y ) (X,Y) ( X , Y ) be a bipartition of G G G and let J = diag ( ε 1 , … , ε n ) J=\operatorname{diag}(\varepsilon_1,\ldots,\varepsilon_n) J = diag ( ε 1 , … , ε n ) with ε i = 1 \varepsilon_i=1 ε i = 1 for i ∈ X i\in X i ∈ X and ε i = − 1 \varepsilon_i=-1 ε i = − 1 for i ∈ Y i\in Y i ∈ Y . Every edge of G G G joins X X X to Y Y Y , so J N F ( G ) J = − N F ( G ) JN_F(G)J=-N_F(G) J N F ( G ) J = − N F ( G ) , and J J J is orthogonal; hence the spectrum of N F ( G ) N_F(G) N F ( G ) is symmetric.
For a graph G G G put
T ( G ) = ∑ { i , j } ∈ E ( G ) δ ( i ) 2 δ ( j ) 2 , (2) T(G)=\sum_{\{i,j\}\in E(G)}\delta(i)^2\delta(j)^2, \tag*{(2)} T ( G ) = { i , j } ∈ E ( G ) ∑ δ ( i ) 2 δ ( j ) 2 , (2)
Lemma 2.7. Let G G G be a graph on n n n vertices and let λ 1 ≥ ⋯ ≥ λ n \lambda_1\ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n be the eigenvalues of N F ( G ) N_F(G) N F ( G ) . Then
∑ i = 1 n λ i = 0 , ∑ i = 1 n λ i 2 = tr ( N F ( G ) 2 ) = 2 T ( G ) , ∑ i < j λ i λ j = − T ( G ) . \sum_{i=1}^{n}\lambda_i=0,\qquad\sum_{i=1}^{n}\lambda_i^2=\operatorname{tr}\left(N_F(G)^2\right)=2T(G),\qquad\sum_{i<j}\lambda_i\lambda_j=-T(G). i = 1 ∑ n λ i = 0 , i = 1 ∑ n λ i 2 = tr ( N F ( G ) 2 ) = 2 T ( G ) , i < j ∑ λ i λ j = − T ( G ) .
Proof. The diagonal of N F ( G ) N_F(G) N F ( G ) is zero, whence ∑ i λ i = tr N F ( G ) = 0 \sum_i\lambda_i=\operatorname{tr}N_F(G)=0 ∑ i λ i = tr N F ( G ) = 0 . Since N F ( G ) N_F(G) N F ( G ) is symmetric, tr ( N F ( G ) 2 ) = ∑ i , j n i j 2 = 2 ∑ { i , j } ∈ E ( G ) δ ( i ) 2 δ ( j ) 2 = 2 T ( G ) \operatorname{tr}\left(N_F(G)^2\right)=\sum_{i,j}n_{ij}^2=2\sum_{\{i,j\}\in E(G)}\delta(i)^2\delta(j)^2=2T(G) tr ( N F ( G ) 2 ) = ∑ i , j n ij 2 = 2 ∑ { i , j } ∈ E ( G ) δ ( i ) 2 δ ( j ) 2 = 2 T ( G ) . Finally 2 ∑ i < j λ i λ j = ( ∑ i λ i ) 2 − ∑ i λ i 2 = − 2 T ( G ) 2\sum_{i<j}\lambda_i\lambda_j=\left(\sum_i\lambda_i\right)^2-\sum_i\lambda_i^2=-2T(G) 2 ∑ i < j λ i λ j = ( ∑ i λ i ) 2 − ∑ i λ i 2 = − 2 T ( G ) .
Proposition 2.8. The following hold.
(i) ρ N F ( K n ) = ( n − 1 ) 5 \rho_{N_F}(K_n)=(n-1)^5 ρ N F ( K n ) = ( n − 1 ) 5 for n ≥ 2 n\ge2 n ≥ 2 .
(ii) ρ N F ( K p , q ) = ( p q ) 2 p q \rho_{N_F}(K_{p,q})=(pq)^2\sqrt{pq} ρ N F ( K p , q ) = ( pq ) 2 pq for p , q ≥ 1 p,q\ge1 p , q ≥ 1 ; in particular ρ N F ( K 1 , n − 1 ) = ( n − 1 ) 2 n − 1 \rho_{N_F}(K_{1,n-1})=(n-1)^2\sqrt{n-1} ρ N F ( K 1 , n − 1 ) = ( n − 1 ) 2 n − 1 .
(iii) ρ N F ( C n ) = 32 \rho_{N_F}(C_n)=32 ρ N F ( C n ) = 32 for every n ≥ 3 n\ge3 n ≥ 3 .
(iv) If G G G is r r r -regular, then ρ N F ( G ) = r 4 ρ ( G ) = r 5 \rho_{N_F}(G)=r^4\rho(G)=r^5 ρ N F ( G ) = r 4 ρ ( G ) = r 5 .
Proof. In each case δ \delta δ is constant, so Proposition 2.4 applies. For K n K_n K n we have δ ≡ ( n − 1 ) 2 \delta\equiv(n-1)^2 δ ≡ ( n − 1 ) 2 and ρ ( K n ) = n − 1 \rho(K_n)=n-1 ρ ( K n ) = n − 1 ; for K p , q K_{p,q} K p , q every vertex satisfies δ ≡ p q \delta\equiv pq δ ≡ pq and ρ ( K p , q ) = p q \rho(K_{p,q})=\sqrt{pq} ρ ( K p , q ) = pq ; for C n C_n C n we have δ ≡ 4 \delta\equiv4 δ ≡ 4 and ρ ( C n ) = 2 \rho(C_n)=2 ρ ( C n ) = 2 , whence ρ N F ( C n ) = 16 ⋅ 2 = 32 \rho_{N_F}(C_n)=16\cdot2=32 ρ N F ( C n ) = 16 ⋅ 2 = 32 ; for an r r r -regular graph δ ≡ r 2 \delta\equiv r^2 δ ≡ r 2 and ρ ( G ) = r \rho(G)=r ρ ( G ) = r .
Note that (iii) shows that ρ N F ( C n ) \rho_{N_F}(C_n) ρ N F ( C n ) does not depend on n n n : all cycles have the same neighbourhood second Zagreb spectral radius.
Bounds for general graphs
We begin with three lemmas describing when δ \delta δ is constant. Recall that a bipartite graph with bipartition ( X , Y ) (X,Y) ( X , Y ) is ( r , s ) (r,s) ( r , s ) -semiregular if every vertex of X X X has degree r r r and every vertex of Y Y Y has degree s s s .
Lemma 3.1. Let G G G be a connected graph on n n n vertices. Then δ \delta δ is constant on V ( G ) V(G) V ( G ) (i.e. δ min = δ max \delta_{\min}=\delta_{\max} δ m i n = δ m a x ) if and only if G G G is regular or bipartite semiregular.
Proof. Assume δ ( i ) = p \delta(i)=p δ ( i ) = p for all i ∈ V ( G ) i\in V(G) i ∈ V ( G ) . Choose k , t ∈ V ( G ) k,t\in V(G) k , t ∈ V ( G ) with d ( k ) = d min d(k)=d_{\min} d ( k ) = d m i n and d ( t ) = d max d(t)=d_{\max} d ( t ) = d m a x . Since every neighbour of k k k has degree at most d max d_{\max} d m a x ,
p = δ ( k ) = ∑ j ∼ k d ( j ) ≤ d ( k ) d max = d min d max . p=\delta(k)=\sum_{j\sim k}d(j)\leq d(k)d_{\max}=d_{\min}d_{\max}. p = δ ( k ) = j ∼ k ∑ d ( j ) ≤ d ( k ) d m a x = d m i n d m a x .
and since every neighbour of t t t has degree at least d min d_{\min} d m i n ,
p = δ ( t ) = ∑ j ∼ t d ( j ) ≥ d ( t ) d min = d max d min . p=\delta(t)=\sum_{j\sim t}d(j)\geq d(t)d_{\min}=d_{\max}d_{\min}. p = δ ( t ) = j ∼ t ∑ d ( j ) ≥ d ( t ) d m i n = d m a x d m i n .
Hence p = d min d max p=d_{\min}d_{\max} p = d m i n d m a x . If d min = d max d_{\min}=d_{\max} d m i n = d m a x , then G G G is regular. Assume therefore d min ≠ d max d_{\min}\ne d_{\max} d m i n = d m a x . From δ ( i ) = d min d max \delta(i)=d_{\min}d_{\max} δ ( i ) = d m i n d m a x for all i i i we deduce: if d ( i ) = d min d(i)=d_{\min} d ( i ) = d m i n , then all neighbours of i i i have degree d max d_{\max} d m a x ; and if d ( i ) = d max d(i)=d_{\max} d ( i ) = d m a x , then all neighbours of i i i have degree d min d_{\min} d m i n . Indeed, in the first case d min d max = δ ( i ) = ∑ j ∼ i d ( j ) ≤ d min d max d_{\min}d_{\max}=\delta(i)=\sum_{j\sim i}d(j)\leq d_{\min}d_{\max} d m i n d m a x = δ ( i ) = ∑ j ∼ i d ( j ) ≤ d m i n d m a x forces d ( j ) = d max d(j)=d_{\max} d ( j ) = d m a x for every j ∼ i j\sim i j ∼ i , and the second case is symmetric.
Fix k k k with d ( k ) = d min d(k)=d_{\min} d ( k ) = d m i n and put V 1 = { k } V_1=\{k\} V 1 = { k } , V l = N G ( V l − 1 ) V_l=N_G(V_{l-1}) V l = N G ( V l − 1 ) for l ≥ 2 l\geq2 l ≥ 2 and V ( G ) = ⋃ l ≥ 1 V l V(G)=\bigcup_{l\geq1}V_l V ( G ) = ⋃ l ≥ 1 V l . By the above, the vertices of V 1 , V 3 , V 5 , … V_1,V_3,V_5,\ldots V 1 , V 3 , V 5 , … have degree d min d_{\min} d m i n and those of V 2 , V 4 , … V_2,V_4,\ldots V 2 , V 4 , … have degree d max d_{\max} d m a x , and every edge joins a vertex of degree d min d_{\min} d m i n to a vertex of degree d max d_{\max} d m a x . Since G G G is connected, V ( G ) = ⋃ m ≥ 1 V m V(G)=\bigcup_{m\geq1}V_m V ( G ) = ⋃ m ≥ 1 V m , and therefore V ( G ) V(G) V ( G ) is partitioned into the set of vertices of degree d min d_{\min} d m i n and the set of vertices of degree d max d_{\max} d m a x , all edges joining the two sets. Thus G G G is ( d min , d max ) (d_{\min},d_{\max}) ( d m i n , d m a x ) -semiregular bipartite.
Conversely, if G G G is r r r -regular, then δ ( i ) = r 2 \delta(i)=r^2 δ ( i ) = r 2 for every i i i ; and if G G G is ( r , s ) (r,s) ( r , s ) -semiregular bipartite, then every vertex is adjacent only to vertices of the opposite part, so δ ( i ) = r s \delta(i)=rs δ ( i ) = r s for every i i i . □
Lemma 3.2 (Favaron et al. [9 ] , Cao [5 ] ). Let G G G be a connected graph on n n n vertices. Then ρ ( G ) ≤ δ max \rho(G)\leq\sqrt{\delta_{\max}} ρ ( G ) ≤ δ m a x , with equality if and only if G G G is regular or bipartite semiregular.
We include the short proof for completeness.
Proof. Let X = ( x 1 , … , x n ) T X=(x_1,\ldots,x_n)^T X = ( x 1 , … , x n ) T be the positive unit eigenvector (Perron vector) of A ( G ) A(G) A ( G ) corresponding to ρ ( G ) \rho(G) ρ ( G ) . For every i i i , the Cauchy–Schwarz inequality gives
ρ ( G ) 2 x i 2 = ( ∑ j ∼ i x j ) 2 ≤ d ( i ) ∑ j ∼ i x j 2 . \rho(G)^2x_i^2=\left(\sum_{j\sim i}x_j\right)^2\leq d(i)\sum_{j\sim i}x_j^2. ρ ( G ) 2 x i 2 = ( j ∼ i ∑ x j ) 2 ≤ d ( i ) j ∼ i ∑ x j 2 .
Summing over i i i and interchanging the order of summation,
ρ ( G ) 2 = ρ ( G ) 2 ∑ i = 1 n x i 2 ≤ ∑ i = 1 n d ( i ) ∑ j ∼ i x j 2 = ∑ j = 1 n x j 2 ∑ i ∼ j d ( i ) = ∑ j = 1 n x j 2 δ ( j ) ≤ δ max . \rho(G)^2=\rho(G)^2\sum_{i=1}^n x_i^2\leq\sum_{i=1}^n d(i)\sum_{j\sim i}x_j^2=\sum_{j=1}^n x_j^2\sum_{i\sim j}d(i)=\sum_{j=1}^n x_j^2\delta(j)\leq\delta_{\max}. ρ ( G ) 2 = ρ ( G ) 2 i = 1 ∑ n x i 2 ≤ i = 1 ∑ n d ( i ) j ∼ i ∑ x j 2 = j = 1 ∑ n x j 2 i ∼ j ∑ d ( i ) = j = 1 ∑ n x j 2 δ ( j ) ≤ δ m a x .
Equality forces δ ( j ) = δ max \delta(j)=\delta_{\max} δ ( j ) = δ m a x for every j j j (the Perron vector is positive), and Lemma 3.1 completes the proof. Conversely, if δ \delta δ is constant, say δ ≡ c \delta\equiv c δ ≡ c , then A 2 1 = c 1 A^2\mathbf{1}=c\mathbf{1} A 2 1 = c 1 ; since 1 > 0 \mathbf{1}>0 1 > 0 , c = ρ ( A 2 ) = ρ ( G ) 2 c=\rho(A^2)=\rho(G)^2 c = ρ ( A 2 ) = ρ ( G ) 2 by the Perron–Frobenius theorem. □
Constancy of the edge weights already forces constancy of δ \delta δ ; this is what turns several equality conditions below into structural characterisations.
Lemma 3.3. Let G G G be a connected graph and suppose that δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) takes one and the same value on every edge of G G G . Then δ \delta δ is constant on V ( G ) V(G) V ( G ) , and hence, by Lemma 3.1 , G G G is regular or bipartite semiregular.
Proof. Let δ ( i ) δ ( j ) = c > 0 \delta(i)\delta(j)=c>0 δ ( i ) δ ( j ) = c > 0 for every { i , j } ∈ E ( G ) \{i,j\}\in E(G) { i , j } ∈ E ( G ) . If two vertices i i i and k k k have a common neighbour j j j , then δ ( i ) δ ( j ) = c = δ ( k ) δ ( j ) \delta(i)\delta(j)=c=\delta(k)\delta(j) δ ( i ) δ ( j ) = c = δ ( k ) δ ( j ) and therefore δ ( i ) = δ ( k ) \delta(i)=\delta(k) δ ( i ) = δ ( k ) . Thus δ \delta δ is constant on each class of the relation “joined by a walk of even length”. If G G G is connected and not bipartite, this relation has a single class and δ \delta δ is constant.
Suppose then that G G G is connected and bipartite with bipartition ( X , Y ) (X,Y) ( X , Y ) , so that δ ≡ a \delta\equiv a δ ≡ a on X X X and δ ≡ b \delta\equiv b δ ≡ b on Y Y Y for some a , b > 0 a,b>0 a , b > 0 . Every edge of G G G has exactly one endpoint in X X X , whence
∑ i ∈ X d ( i ) δ ( i ) = ∑ i ∈ X ∑ j ∼ i d ( i ) d ( j ) = ∑ { i , j } ∈ E ( G ) d ( i ) d ( j ) = M 2 ( G ) , \sum_{i\in X}d(i)\delta(i)=\sum_{i\in X}\sum_{j\sim i}d(i)d(j)=\sum_{\{i,j\}\in E(G)}d(i)d(j)=M_2(G), i ∈ X ∑ d ( i ) δ ( i ) = i ∈ X ∑ j ∼ i ∑ d ( i ) d ( j ) = { i , j } ∈ E ( G ) ∑ d ( i ) d ( j ) = M 2 ( G ) ,
M 2 M_2 M 2 denoting the second Zagreb index, and the same computation over Y Y Y gives ∑ j ∈ Y d ( j ) δ ( j ) = M 2 ( G ) \sum_{j\in Y}d(j)\delta(j)=M_2(G) ∑ j ∈ Y d ( j ) δ ( j ) = M 2 ( G ) . Consequently a ∑ i ∈ X d ( i ) = b ∑ j ∈ Y d ( j ) a\sum_{i\in X}d(i)=b\sum_{j\in Y}d(j) a ∑ i ∈ X d ( i ) = b ∑ j ∈ Y d ( j ) , and since ∑ i ∈ X d ( i ) = ∑ j ∈ Y d ( j ) = m > 0 \sum_{i\in X}d(i)=\sum_{j\in Y}d(j)=m>0 ∑ i ∈ X d ( i ) = ∑ j ∈ Y d ( j ) = m > 0 we conclude a = b a=b a = b .
Theorem 3.4 (cf. [1 Cor. 4] ). Let G G G be a connected graph on n n n vertices. Then
ρ N F ( G ) ≤ d max 5 , \rho_{N_F}(G)\le d_{\max}^{5}, ρ N F ( G ) ≤ d m a x 5 , and equality holds if and only if G G G is regular.
Proof. By (1) , δ ( i ) ≤ d max 2 \delta(i)\le d_{\max}^{2} δ ( i ) ≤ d m a x 2 for every i i i . The i i i -th row sum of N F ( G ) N_F(G) N F ( G ) equals
R i = δ ( i ) ∑ j ∼ i δ ( j ) ≤ d max 2 ⋅ d ( i ) d max 2 ≤ d max 5 . (3) R_i=\delta(i)\sum_{j\sim i}\delta(j)\le d_{\max}^{2}\cdot d(i)d_{\max}^{2}\le d_{\max}^{5}. \tag*{(3)} R i = δ ( i ) j ∼ i ∑ δ ( j ) ≤ d m a x 2 ⋅ d ( i ) d m a x 2 ≤ d m a x 5 . (3)
Since N F ( G ) N_F(G) N F ( G ) is nonnegative and irreducible, Lemma 2.2 yields ρ N F ( G ) ≤ max i R i ≤ d max 5 \rho_{N_F}(G)\le\max_i R_i\le d_{\max}^{5} ρ N F ( G ) ≤ max i R i ≤ d m a x 5 .
If ρ N F ( G ) = d max 5 \rho_{N_F}(G)=d_{\max}^{5} ρ N F ( G ) = d m a x 5 , then max i R i = d max 5 = ρ N F ( G ) \max_i R_i=d_{\max}^{5}=\rho_{N_F}(G) max i R i = d m a x 5 = ρ N F ( G ) , so by Lemma 2.2 all row sums are equal to d max 5 d_{\max}^{5} d m a x 5 . Hence, both inequalities in (3) are equalities for every i i i , which forces δ ( i ) = d max 2 \delta(i)=d_{\max}^{2} δ ( i ) = d m a x 2 and d ( i ) = d max d(i)=d_{\max} d ( i ) = d m a x for every i ∈ V ( G ) i\in V(G) i ∈ V ( G ) ; that is, G G G is regular. Conversely, if G G G is d max d_{\max} d m a x -regular, then ρ N F ( G ) = d max 5 \rho_{N_F}(G)=d_{\max}^{5} ρ N F ( G ) = d m a x 5 by Proposition 2.8 (iv).
Remark 3.5. Since d max ≤ n − 1 d_{\max}\le n-1 d m a x ≤ n − 1 , Theorem 3.4 also gives ρ N F ( G ) ≤ ( n − 1 ) 5 \rho_{N_F}(G)\le(n-1)^5 ρ N F ( G ) ≤ ( n − 1 ) 5 , with equality if and only if G ≅ K n G\cong K_n G ≅ K n . For sparse graphs the degree-based bound is far better: for a graph on n = 100 n=100 n = 100 vertices with d max = 10 d_{\max}=10 d m a x = 10 one gets ρ N F ( G ) ≤ 10 5 \rho_{N_F}(G)\le10^5 ρ N F ( G ) ≤ 1 0 5 , while the bound in terms of n n n only gives 99 5 99^5 9 9 5 .
Theorem 3.4 is an upper estimate. We now give a lower estimate in terms of the adjacency spectral radius alone; besides its own interest, it is the key to the equality case of Theorem 3.8 below.
Theorem 3.6. Let G G G be a connected graph on n ≥ 2 n\ge2 n ≥ 2 vertices. Then
ρ N F ( G ) ≥ ρ ( G ) 5 , \rho_{N_F}(G)\ge\rho(G)^5, ρ N F ( G ) ≥ ρ ( G ) 5 , and equality holds if and only if G G G is regular or bipartite semiregular.
Proof. Write ρ = ρ ( G ) > 0 \rho=\rho(G)>0 ρ = ρ ( G ) > 0 and A = A ( G ) A=A(G) A = A ( G ) , let ξ = ( ξ 1 , … , ξ n ) T \boldsymbol{\xi}=(\xi_1,\ldots,\xi_n)^{T} ξ = ( ξ 1 , … , ξ n ) T be the positive unit eigenvector of A A A corresponding to ρ \rho ρ , and put Q = A 2 Q=A^2 Q = A 2 . The entry Q i j Q_{ij} Q ij is the number of walks of length 2 from i i i to j j j , so Q Q Q is nonnegative and symmetric and ∑ j Q i j = ∑ k ∼ i d ( k ) = δ ( i ) \sum_j Q_{ij}=\sum_{k\sim i}d(k)=\delta(i) ∑ j Q ij = ∑ k ∼ i d ( k ) = δ ( i ) . Moreover δ ( i ) > 0 \delta(i)>0 δ ( i ) > 0 for every i i i , so D δ = diag ( δ ( 1 ) , … , δ ( n ) ) D_{\delta}=\operatorname{diag}(\delta(1),\ldots,\delta(n)) D δ = diag ( δ ( 1 ) , … , δ ( n )) is invertible.
Step 1: ∑ i ξ i 2 / δ ( i ) ≤ 1 / ρ 2 \sum_i \xi_i^2/\delta(i)\le1/\rho^2 ∑ i ξ i 2 / δ ( i ) ≤ 1/ ρ 2 . For every x ∈ R n x\in\mathbb{R}^n x ∈ R n ,
x T ( D δ − Q ) x = ∑ i δ ( i ) x i 2 − ∑ i , j Q i j x i x j = 1 2 ∑ i , j Q i j ( x i − x j ) 2 ≥ 0. x^{T}(D_{\delta}-Q)x=\sum_i\delta(i)x_i^2-\sum_{i,j}Q_{ij}x_ix_j=\frac{1}{2}\sum_{i,j}Q_{ij}(x_i-x_j)^2\ge0. x T ( D δ − Q ) x = i ∑ δ ( i ) x i 2 − i , j ∑ Q ij x i x j = 2 1 i , j ∑ Q ij ( x i − x j ) 2 ≥ 0.
and x T Q x = ∥ A x ∥ 2 ≥ 0 x^{T}Qx=\lVert Ax\rVert^{2}\ge0 x T Q x = ∥ A x ∥ 2 ≥ 0 . Hence the symmetric matrix Γ = D δ − 1 / 2 Q D δ − 1 / 2 \Gamma=D_{\delta}^{-1/2}QD_{\delta}^{-1/2} Γ = D δ − 1/2 Q D δ − 1/2 satisfies 0 ⪯ Γ ⪯ I 0\preceq\Gamma\preceq I 0 ⪯ Γ ⪯ I , so all its eigenvalues lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] and Γ 2 ⪯ Γ \Gamma^{2}\preceq\Gamma Γ 2 ⪯ Γ . Put q = D δ 1 / 2 ξ q=D_{\delta}^{1/2}\xi q = D δ 1/2 ξ . Then Γ q = D δ − 1 / 2 Q ξ = ρ 2 D δ − 1 / 2 ξ \Gamma q=D_{\delta}^{-1/2}Q\xi=\rho^{2}D_{\delta}^{-1/2}\xi Γ q = D δ − 1/2 Q ξ = ρ 2 D δ − 1/2 ξ and q T Γ q = ξ T Q ξ = ρ 2 q^{T}\Gamma q=\xi^{T}Q\xi=\rho^{2} q T Γ q = ξ T Q ξ = ρ 2 , so
ρ 4 ∑ i ξ i 2 δ ( i ) = ∥ Γ q ∥ 2 = q T Γ 2 q ≤ q T Γ q = ρ 2 . \rho^{4}\sum_i\frac{\xi_i^2}{\delta(i)}=\lVert\Gamma q\rVert^{2}=q^{T}\Gamma^{2}q\le q^{T}\Gamma q=\rho^{2}. ρ 4 i ∑ δ ( i ) ξ i 2 = ∥ Γ q ∥ 2 = q T Γ 2 q ≤ q T Γ q = ρ 2 .
Step 2. Put ℓ = ∑ i ξ i 2 log δ ( i ) \ell=\sum_i\xi_i^2\log\delta(i) ℓ = ∑ i ξ i 2 log δ ( i ) . Since ∑ i ξ i 2 = 1 \sum_i\xi_i^2=1 ∑ i ξ i 2 = 1 , Jensen’s inequality for the concave function log \log log and Step 1 give
− ℓ = ∑ i ξ i 2 log 1 δ ( i ) ≤ log ∑ i ξ i 2 δ ( i ) ≤ − log ρ 2 , that is, e ℓ ≥ ρ 2 . -\ell=\sum_i\xi_i^2\log\frac{1}{\delta(i)}\le\log\sum_i\frac{\xi_i^2}{\delta(i)}\le-\log\rho^2,\qquad\text{that is,}\qquad e^\ell\ge\rho^2. − ℓ = i ∑ ξ i 2 log δ ( i ) 1 ≤ log i ∑ δ ( i ) ξ i 2 ≤ − log ρ 2 , that is, e ℓ ≥ ρ 2 .
Step 3: ξ T N F ξ ≥ ρ e 2 ℓ \xi^{T}N_F\xi\ge\rho e^{2\ell} ξ T N F ξ ≥ ρ e 2 ℓ . For every edge { i , j } \{i,j\} { i , j } put x i j = log δ ( i ) + log δ ( j ) − 2 ℓ x_{ij}=\log\delta(i)+\log\delta(j)-2\ell x ij = log δ ( i ) + log δ ( j ) − 2 ℓ , so that δ ( i ) δ ( j ) e − 2 ℓ = e x i j ≥ 1 + x i j \delta(i)\delta(j)e^{-2\ell}=e^{x_{ij}}\ge1+x_{ij} δ ( i ) δ ( j ) e − 2 ℓ = e x ij ≥ 1 + x ij , with equality if and only if x i j = 0 x_{ij}=0 x ij = 0 . Multiplying by a i j ξ i ξ j a_{ij}\xi_i\xi_j a ij ξ i ξ j , which is positive when i ∼ j i\sim j i ∼ j , and summing over all ordered pairs ( i , j ) (i,j) ( i , j ) , we obtain
e − 2 ℓ ξ T N F ξ ≥ ∑ i , j a i j ξ i ξ j + ∑ i , j a i j ξ i ξ j [ ( log δ ( i ) − ℓ ) + ( log δ ( j ) − ℓ ) ] = ρ + 2 ρ ∑ i ξ i 2 ( log δ ( i ) − ℓ ) = ρ , \begin{aligned}
e^{-2\ell}\xi^{T}N_F\xi\ge\sum_{i,j}a_{ij}\xi_i\xi_j+\sum_{i,j}a_{ij}\xi_i\xi_j\left[(\log\delta(i)-\ell)+(\log\delta(j)-\ell)\right] \\
&=\rho+2\rho\sum_i\xi_i^2(\log\delta(i)-\ell)=\rho,
\end{aligned} e − 2 ℓ ξ T N F ξ ≥ i , j ∑ a ij ξ i ξ j + i , j ∑ a ij ξ i ξ j [ ( log δ ( i ) − ℓ ) + ( log δ ( j ) − ℓ ) ] = ρ + 2 ρ i ∑ ξ i 2 ( log δ ( i ) − ℓ ) = ρ ,
because ∑ j a i j ξ j = ρ ξ i \sum_j a_{ij}\xi_j=\rho\xi_i ∑ j a ij ξ j = ρ ξ i and ∑ i ξ i 2 ( log δ ( i ) − ℓ ) = ℓ − ℓ = 0 \sum_i\xi_i^2(\log\delta(i)-\ell)=\ell-\ell=0 ∑ i ξ i 2 ( log δ ( i ) − ℓ ) = ℓ − ℓ = 0 .
Step 4. By Lemma 2.1, Step 3 and Step 2,
ρ N F ( G ) ≥ ξ T N F ξ ≥ ρ e 2 ℓ ≥ ρ ⋅ ρ 4 = ρ 5 . \rho_{N_F}(G)\ge\xi^{T}N_F\xi\ge\rho e^{2\ell}\ge\rho\cdot\rho^4=\rho^5. ρ N F ( G ) ≥ ξ T N F ξ ≥ ρ e 2 ℓ ≥ ρ ⋅ ρ 4 = ρ 5 .
Equality. If ρ N F ( G ) = ρ 5 \rho_{N_F}(G)=\rho^5 ρ N F ( G ) = ρ 5 , then equality holds in Step 3, so x i j = 0 x_{ij}=0 x ij = 0 for every edge, i.e. δ ( i ) δ ( j ) = e 2 ℓ \delta(i)\delta(j)=e^{2\ell} δ ( i ) δ ( j ) = e 2 ℓ for every { i , j } ∈ E ( G ) \{i,j\}\in E(G) { i , j } ∈ E ( G ) . By Lemma 3.3, G G G is regular or bipartite semiregular. Conversely, if G G G is regular or bipartite semiregular, then δ ≡ c \delta\equiv c δ ≡ c by Lemma 3.1, ρ 2 = c \rho^2=c ρ 2 = c by Lemma 3.2, and ρ N F ( G ) = c 2 ρ = ρ 5 \rho_{N_F}(G)=c^2\rho=\rho^5 ρ N F ( G ) = c 2 ρ = ρ 5 by Proposition 2.4.
Theorem 3.4 is a row-sum estimate. Weighting the rows against each other gives a bound of the Berman–Zhang type [3 ] which is never weaker (Remark 3.9). For its equality case we need the following estimate for graphs whose row sums R i R_i R i are constant on the classes of vertices joined by walks of even length.
Lemma 3.7. Let G G G be a connected graph on n ≥ 2 n\ge2 n ≥ 2 vertices and let R i = δ ( i ) ∑ j ∼ i δ ( j ) R_i=\delta(i)\sum_{j\sim i}\delta(j) R i = δ ( i ) ∑ j ∼ i δ ( j ) be the i i i -th row sum of N F ( G ) N_F(G) N F ( G ) .
(i) If R i = R 0 R_i=R_0 R i = R 0 for every i ∈ V ( G ) i\in V(G) i ∈ V ( G ) , then R 0 ≤ ρ ( G ) 5 R_0\le\rho(G)^5 R 0 ≤ ρ ( G ) 5 .
(ii) If G G G is bipartite with bipartition ( X , Y ) (X,Y) ( X , Y ) , and R i = R X R_i=R_X R i = R X for i ∈ X i\in X i ∈ X and R i = R Y R_i=R_Y R i = R Y for i ∈ Y i\in Y i ∈ Y , then R X R Y ≤ ρ ( G ) 10 R_XR_Y\le\rho(G)^{10} R X R Y ≤ ρ ( G ) 10 .
Proof. Write ρ = ρ ( G ) \rho=\rho(G) ρ = ρ ( G ) , A = A ( G ) A=A(G) A = A ( G ) and σ ( i ) = ∑ j ∼ i δ ( j ) \sigma(i)=\sum_{j\sim i}\delta(j) σ ( i ) = ∑ j ∼ i δ ( j ) , so that R i = δ ( i ) σ ( i ) R_i=\delta(i)\sigma(i) R i = δ ( i ) σ ( i ) ; in vector form δ = ( δ ( 1 ) , ⋯ , δ ( n ) ) T = A 2 1 \boldsymbol{\delta}=(\delta(1),\cdots,\delta(n))^{T}=A^{2}\boldsymbol{1} δ = ( δ ( 1 ) , ⋯ , δ ( n ) ) T = A 2 1 and σ = A δ \boldsymbol{\sigma}=A\boldsymbol{\delta} σ = A δ . Let ξ > 0 \xi>0 ξ > 0 be an eigenvector of A A A belonging to ρ \rho ρ .
(i) We have ξ T δ = ( A 2 ξ ) T 1 = ρ 2 ∑ i ξ i \xi^{T}\boldsymbol{\delta}=(A^{2}\xi)^{T}\boldsymbol{1}=\rho^{2}\sum_i\xi_i ξ T δ = ( A 2 ξ ) T 1 = ρ 2 ∑ i ξ i and ξ T σ = ( A ξ ) T δ = ρ ξ T δ = ρ 3 ∑ i ξ i \xi^{T}\boldsymbol{\sigma}=(A\xi)^{T}\boldsymbol{\delta}=\rho\,\xi^{T}\boldsymbol{\delta}=\rho^{3}\sum_i\xi_i ξ T σ = ( A ξ ) T δ = ρ ξ T δ = ρ 3 ∑ i ξ i . Since σ ( i ) = R 0 / δ ( i ) \sigma(i)=R_0/\delta(i) σ ( i ) = R 0 / δ ( i ) , this gives ∑ i ξ i / δ ( i ) = ( ρ 3 / R 0 ) ∑ i ξ i \sum_i\xi_i/\delta(i)=(\rho^3/R_0)\sum_i\xi_i ∑ i ξ i / δ ( i ) = ( ρ 3 / R 0 ) ∑ i ξ i . By the Cauchy–Schwarz inequality,
( ∑ i ξ i ) 2 = ( ∑ i ξ i δ ( i ) ξ i δ ( i ) ) 2 ≤ ( ∑ i ξ i δ ( i ) ) ( ∑ i ξ i δ ( i ) ) = ρ 5 R 0 ( ∑ i ξ i ) 2 . \left(\sum_i\xi_i\right)^2=\left(\sum_i\sqrt{\xi_i\delta(i)}\sqrt{\frac{\xi_i}{\delta(i)}}\right)^2\le\left(\sum_i\xi_i\delta(i)\right)\left(\sum_i\frac{\xi_i}{\delta(i)}\right)=\frac{\rho^5}{R_0}\left(\sum_i\xi_i\right)^2. ( i ∑ ξ i ) 2 = ( i ∑ ξ i δ ( i ) δ ( i ) ξ i ) 2 ≤ ( i ∑ ξ i δ ( i ) ) ( i ∑ δ ( i ) ξ i ) = R 0 ρ 5 ( i ∑ ξ i ) 2 .
So R 0 ≤ ρ 5 R_0\le\rho^5 R 0 ≤ ρ 5 . (ii) Let ξ X \xi_X ξ X and ξ Y \xi_Y ξ Y be the vectors that agree with ξ \xi ξ on X X X and on Y Y Y , respectively, and vanish elsewhere. Since every edge joins X X X to Y Y Y , we have A ξ X = ρ ξ Y A\xi_X=\rho\xi_Y A ξ X = ρ ξ Y and A ξ Y = ρ ξ X A\xi_Y=\rho\xi_X A ξ Y = ρ ξ X , hence A 2 ξ X = ρ 2 ξ X A^2\xi_X=\rho^2\xi_X A 2 ξ X = ρ 2 ξ X and A 2 ξ Y = ρ 2 ξ Y A^2\xi_Y=\rho^2\xi_Y A 2 ξ Y = ρ 2 ξ Y . Therefore
∑ i ∈ X ξ i δ ( i ) = ( A 2 ξ X ) T 1 = ρ 2 ∑ i ∈ X ξ i , ∑ i ∈ X ξ i σ ( i ) = ( A ξ X ) T δ = ρ ∑ j ∈ Y ξ j δ ( j ) = ρ 3 ∑ j ∈ Y ξ j . \sum_{i\in X}\xi_i\delta(i)=(A^2\xi_X)^T\mathbf{1}=\rho^2\sum_{i\in X}\xi_i,\qquad\sum_{i\in X}\xi_i\sigma(i)=(A\xi_X)^T\delta=\rho\sum_{j\in Y}\xi_j\delta(j)=\rho^3\sum_{j\in Y}\xi_j. i ∈ X ∑ ξ i δ ( i ) = ( A 2 ξ X ) T 1 = ρ 2 i ∈ X ∑ ξ i , i ∈ X ∑ ξ i σ ( i ) = ( A ξ X ) T δ = ρ j ∈ Y ∑ ξ j δ ( j ) = ρ 3 j ∈ Y ∑ ξ j .
As σ ( i ) = R X / δ ( i ) \sigma(i)=R_X/\delta(i) σ ( i ) = R X / δ ( i ) for i ∈ X i\in X i ∈ X , the Cauchy–Schwarz inequality over X X X gives
( ∑ i ∈ X ξ i ) 2 ≤ ( ∑ i ∈ X ξ i δ ( i ) ) ( ∑ i ∈ X ξ i δ ( i ) ) = ρ 2 ∑ i ∈ X ξ i ⋅ ρ 3 R X ∑ j ∈ Y ξ j , \left(\sum_{i\in X}\xi_i\right)^2\leq\left(\sum_{i\in X}\xi_i\delta(i)\right)\left(\sum_{i\in X}\frac{\xi_i}{\delta(i)}\right)=\rho^2\sum_{i\in X}\xi_i\cdot\frac{\rho^3}{R_X}\sum_{j\in Y}\xi_j, ( i ∈ X ∑ ξ i ) 2 ≤ ( i ∈ X ∑ ξ i δ ( i ) ) ( i ∈ X ∑ δ ( i ) ξ i ) = ρ 2 i ∈ X ∑ ξ i ⋅ R X ρ 3 j ∈ Y ∑ ξ j ,
that is, R X ∑ i ∈ X ξ i ≤ ρ 5 ∑ j ∈ Y ξ j R_X\sum_{i\in X}\xi_i\leq\rho^5\sum_{j\in Y}\xi_j R X ∑ i ∈ X ξ i ≤ ρ 5 ∑ j ∈ Y ξ j . By symmetry, R Y ∑ j ∈ Y ξ j ≤ ρ 5 ∑ i ∈ X ξ i R_Y\sum_{j\in Y}\xi_j\leq\rho^5\sum_{i\in X}\xi_i R Y ∑ j ∈ Y ξ j ≤ ρ 5 ∑ i ∈ X ξ i . Multiplying these two inequalities between positive numbers gives R X R Y ≤ ρ 10 R_XR_Y\leq\rho^{10} R X R Y ≤ ρ 10 .
Theorem 3.8. Let G G G be a connected graph on n ≥ 2 n\geq2 n ≥ 2 vertices and, for i ∈ V ( G ) i\in V(G) i ∈ V ( G ) , let R i = δ ( i ) ∑ j ∼ i δ ( j ) R_i=\delta(i)\sum_{j\sim i}\delta(j) R i = δ ( i ) ∑ j ∼ i δ ( j ) be the i i i -th row sum of N F ( G ) N_F(G) N F ( G ) . Put
β ( G ) = max { i , j } ∈ E ( G ) R i R j . \beta(G)=\max_{\{i,j\}\in E(G)}\sqrt{R_iR_j}. β ( G ) = { i , j } ∈ E ( G ) max R i R j . Then ρ N F ( G ) ≤ β ( G ) \rho_{N_F}(G)\leq\beta(G) ρ N F ( G ) ≤ β ( G ) . Moreover, equality holds if and only if G G G is regular or G G G is bipartite semiregular.
Proof. Let z = ( R 1 , … , R n ) T > 0 z=(\sqrt{R_1},\ldots,\sqrt{R_n})^T>0 z = ( R 1 , … , R n ) T > 0 and let π > 0 \pi>0 π > 0 be a Perron vector of N F ( G ) N_F(G) N F ( G ) , so that N F π = ρ N F ( G ) π N_F\pi=\rho_{N_F}(G)\pi N F π = ρ N F ( G ) π .
Step 1: the inequality. For every i i i ,
( N F z ) i = ∑ j ∼ i δ ( i ) δ ( j ) R j ≤ ( I ) R i max j ∼ i R j ≤ ( I I ) β ( G ) R i , (4) (N_Fz)_i=\sum_{j\sim i}\delta(i)\delta(j)\sqrt{R_j}\mathrel{\underset{\mathrm{(I)}}{\leq}}R_i\max_{j\sim i}\sqrt{R_j}\mathrel{\underset{\mathrm{(II)}}{\leq}}\beta(G)\sqrt{R_i}, \tag*{(4)} ( N F z ) i = j ∼ i ∑ δ ( i ) δ ( j ) R j ( I ) ≤ R i j ∼ i max R j ( II ) ≤ β ( G ) R i , (4) where (I) uses ∑ j ∼ i δ ( i ) δ ( j ) = R i \sum_{j\sim i}\delta(i)\delta(j)=R_i ∑ j ∼ i δ ( i ) δ ( j ) = R i , and (II) holds because R i max j ∼ i R j \sqrt{R_i}\max_{j\sim i}\sqrt{R_j} R i max j ∼ i R j is one of the numbers R i R j \sqrt{R_iR_j} R i R j , j ∼ i j\sim i j ∼ i . Thus N F z ≤ β ( G ) z N_Fz\leq\beta(G)z N F z ≤ β ( G ) z entrywise. Since N F N_F N F is symmetric,
ρ N F ( G ) π T z = π T N F z ≤ β ( G ) π T z , (5) \rho_{N_F}(G)\pi^Tz=\pi^TN_Fz\leq\beta(G)\pi^Tz, \tag*{(5)} ρ N F ( G ) π T z = π T N F z ≤ β ( G ) π T z , (5) and π T z > 0 \pi^Tz>0 π T z > 0 gives ρ N F ( G ) ≤ β ( G ) \rho_{N_F}(G)\leq\beta(G) ρ N F ( G ) ≤ β ( G ) .
Step 2: regular and bipartite semiregular graphs attain equality. If G G G is regular or bipartite semiregular, then δ ≡ c \delta\equiv c δ ≡ c by Lemma 3.1 , and d ( i ) d ( j ) = c d(i)d(j)=c d ( i ) d ( j ) = c on every edge (r ⋅ r = r 2 r\cdot r=r^2 r ⋅ r = r 2 for an r r r -regular graph, r s rs r s for an ( r , s ) (r,s) ( r , s ) -semiregular bipartite graph). Hence R i = c ⋅ c d ( i ) = c 2 d ( i ) R_i=c\cdot cd(i)=c^2d(i) R i = c ⋅ c d ( i ) = c 2 d ( i ) and R i R j = c 2 d ( i ) d ( j ) = c 5 / 2 \sqrt{R_iR_j}=c^2\sqrt{d(i)d(j)}=c^{5/2} R i R j = c 2 d ( i ) d ( j ) = c 5/2 for every edge, so β ( G ) = c 5 / 2 \beta(G)=c^{5/2} β ( G ) = c 5/2 . By Proposition 2.4 and Lemma 3.2 , ρ N F ( G ) = c 2 ρ ( G ) = c 2 c = β ( G ) \rho_{N_F}(G)=c^2\rho(G)=c^2\sqrt{c}=\beta(G) ρ N F ( G ) = c 2 ρ ( G ) = c 2 c = β ( G ) .
Step 3: equality forces R R R to be constant on the classes of even walks. Suppose ρ N F ( G ) = β ( G ) \rho_{N_F}(G)=\beta(G) ρ N F ( G ) = β ( G ) . Then equality holds in (5) , i.e. π T ( β ( G ) z − N F z ) = 0 \pi^T(\beta(G)z-N_Fz)=0 π T ( β ( G ) z − N F z ) = 0 ; as π > 0 \pi>0 π > 0 and β ( G ) z − N F z ≥ 0 \beta(G)z-N_Fz\geq0 β ( G ) z − N F z ≥ 0 , we get N F z = β ( G ) z N_Fz=\beta(G)z N F z = β ( G ) z , so (I) in (4) is an equality for every i i i . The weights δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) are positive, and a weighted average equals the maximum of the averaged values only if all of them are equal; hence all neighbours of each vertex have the same value of R R R . If j j j is a common neighbour of i i i and k k k , then i i i and k k k are both neighbours of j j j , so R i = R k R_i=R_k R i = R k . Consequently R R R is constant on every class of vertices joined by walks of even length. If G G G is not bipartite, any two vertices are joined by an even walk, so R ≡ R 0 R\equiv R_0 R ≡ R 0 on V ( G ) V(G) V ( G ) and β ( G ) = R 0 \beta(G)=R_0 β ( G ) = R 0 . If G G G is bipartite with bipartition ( X , Y ) (X,Y) ( X , Y ) , then R ≡ R X R\equiv R_X R ≡ R X on X X X and R ≡ R Y R\equiv R_Y R ≡ R Y on Y Y Y , every edge joins X X X to Y Y Y , and β ( G ) = R X R Y \beta(G)=\sqrt{R_XR_Y} β ( G ) = R X R Y .
Step 4: equality forces G G G to be regular or bipartite semiregular. In either case of Step 3, Lemma 3.7 gives β ( G ) ≤ ρ ( G ) 5 \beta(G)\leq\rho(G)^5 β ( G ) ≤ ρ ( G ) 5 . Together with Theorem 3.6 ,
ρ ( G ) 5 ≤ ρ N F ( G ) = β ( G ) ≤ ρ ( G ) 5 , \rho(G)^5\leq\rho_{N_F}(G)=\beta(G)\leq\rho(G)^5, ρ ( G ) 5 ≤ ρ N F ( G ) = β ( G ) ≤ ρ ( G ) 5 , so ρ N F ( G ) = ρ ( G ) 5 \rho_{N_F}(G)=\rho(G)^5 ρ N F ( G ) = ρ ( G ) 5 , and the equality part of Theorem 3.6 shows that G G G is regular or bipartite semiregular. Together with Step 2 this proves the equivalence.
Remark 3.9. (a) Since R i R j ≤ max k R k \sqrt{R_iR_j}\le\max_k R_k R i R j ≤ max k R k and, by (3) , R k ≤ d max 5 R_k\le d_{\max}^{5} R k ≤ d m a x 5 , Theorem 3.8 yields
ρ N F ( G ) ≤ β ( G ) ≤ max i ∈ V ( G ) R i ≤ d max 5 . \rho_{NF}(G)\le\beta(G)\le\max_{i\in V(G)}R_i\le d_{\max}^{5}. ρ N F ( G ) ≤ β ( G ) ≤ i ∈ V ( G ) max R i ≤ d m a x 5 .
Thus it refines both the row-sum bound of Lemma 2.2 (b) and Theorem 3.4 . In the regular case all four quantities equal r 5 r^{5} r 5 ; for the star K 1 , n − 1 K_{1,n-1} K 1 , n − 1 one has β = ( n − 1 ) 5 / 2 = ρ N F \beta=(n-1)^{5/2}=\rho_{NF} β = ( n − 1 ) 5/2 = ρ N F , whereas max i R i = ( n − 1 ) 3 \max_i R_i=(n-1)^3 max i R i = ( n − 1 ) 3 and d max 5 = ( n − 1 ) 5 d_{\max}^{5}=(n-1)^5 d m a x 5 = ( n − 1 ) 5 .
(b) Unlike Theorem 3.4 , the bound of Theorem 3.8 is not dominated by Corollary 3.12: for the star K 1 , n − 1 K_{1,n-1} K 1 , n − 1 both give the exact value ( n − 1 ) 5 / 2 (n-1)^{5/2} ( n − 1 ) 5/2 , whereas for many graphs each is the smaller one. Among the 141 connected graphs on 3 to 6 vertices, β ( G ) < δ max 5 / 2 \beta(G)<\delta_{\max}^{5/2} β ( G ) < δ m a x 5/2 for 100, β ( G ) = δ max 5 / 2 \beta(G)=\delta_{\max}^{5/2} β ( G ) = δ m a x 5/2 for 17 and β ( G ) > δ max 5 / 2 \beta(G)>\delta_{\max}^{5/2} β ( G ) > δ m a x 5/2 for 24.
The following theorem relates ρ N F ( G ) \rho_{NF}(G) ρ N F ( G ) and ρ ( G ) \rho(G) ρ ( G ) . In [1 Theorem 9] equality on either side is asserted to hold if and only if G G G is regular. This is incomplete: every bipartite semiregular graph attains equality as well; for instance, for the stars K 1 , n − 1 K_{1,n-1} K 1 , n − 1 one has δ = n − 1 \delta=n-1 δ = n − 1 and N F = ( n − 1 ) 2 A N_F=(n-1)^2A N F = ( n − 1 ) 2 A . The corrected statement is as follows.
Theorem 3.10. Let G G G be a connected graph. Then
δ min 2 ρ ( G ) ≤ ρ N F ( G ) ≤ δ max 2 ρ ( G ) . \delta_{\min}^{2}\rho(G)\le\rho_{NF}(G)\le\delta_{\max}^{2}\rho(G). δ m i n 2 ρ ( G ) ≤ ρ N F ( G ) ≤ δ m a x 2 ρ ( G ) . Equality holds in either inequality if and only if G G G is regular or bipartite semiregular.
Proof. Let X = ( x 1 , … , x n ) T X=(x_1,\ldots,x_n)^T X = ( x 1 , … , x n ) T be the (positive) unit Perron vector of N F ( G ) N_F(G) N F ( G ) . By Lemma 2.1 ,
ρ N F ( G ) = X T N F X = 2 ∑ { i , j } ∈ E ( G ) δ ( i ) δ ( j ) x i x j ≤ 2 δ max 2 ∑ { i , j } ∈ E ( G ) x i x j = δ max 2 X T A ( G ) X ≤ δ max 2 ρ ( G ) . \begin{aligned}
\rho_{NF}(G)&=X^TN_FX=2\sum_{\{i,j\}\in E(G)}\delta(i)\delta(j)x_ix_j\le2\delta_{\max}^{2}\sum_{\{i,j\}\in E(G)}x_ix_j\\
&=\delta_{\max}^{2}X^TA(G)X\le\delta_{\max}^{2}\rho(G).
\end{aligned} ρ N F ( G ) = X T N F X = 2 { i , j } ∈ E ( G ) ∑ δ ( i ) δ ( j ) x i x j ≤ 2 δ m a x 2 { i , j } ∈ E ( G ) ∑ x i x j = δ m a x 2 X T A ( G ) X ≤ δ m a x 2 ρ ( G ) .
Since X > 0 X>0 X > 0 , equality in the middle step holds if and only if δ ( i ) δ ( j ) = δ max 2 \delta(i)\delta(j)=\delta_{\max}^{2} δ ( i ) δ ( j ) = δ m a x 2 for every edge { i , j } \{i,j\} { i , j } , i.e. if and only if δ ≡ δ max \delta\equiv\delta_{\max} δ ≡ δ m a x ; by Lemma 3.1 this happens exactly when G G G is regular or bipartite semiregular.
Similarly, if Y = ( y 1 , … , y n ) T Y=(y_1,\ldots,y_n)^T Y = ( y 1 , … , y n ) T denotes the positive unit Perron vector of A ( G ) A(G) A ( G ) , then
ρ N F ( G ) ≥ Y T N F Y = 2 ∑ { i , j } ∈ E ( G ) δ ( i ) δ ( j ) y i y j ≥ 2 δ min 2 ∑ { i , j } ∈ E ( G ) y i y j = δ min 2 Y T A ( G ) Y = δ min 2 ρ ( G ) , \begin{aligned}
\rho_{NF}(G)&\ge Y^TN_FY=2\sum_{\{i,j\}\in E(G)}\delta(i)\delta(j)y_iy_j\ge2\delta_{\min}^{2}\sum_{\{i,j\}\in E(G)}y_iy_j\\
&=\delta_{\min}^{2}Y^TA(G)Y=\delta_{\min}^{2}\rho(G),
\end{aligned} ρ N F ( G ) ≥ Y T N F Y = 2 { i , j } ∈ E ( G ) ∑ δ ( i ) δ ( j ) y i y j ≥ 2 δ m i n 2 { i , j } ∈ E ( G ) ∑ y i y j = δ m i n 2 Y T A ( G ) Y = δ m i n 2 ρ ( G ) ,
and equality holds if and only if δ ≡ δ min \delta\equiv\delta_{\min} δ ≡ δ m i n , that is, again if and only if G G G is regular or bipartite semiregular.
Remark 3.11. Write ρ Υ ( G ) \rho_{\Upsilon}(G) ρ Υ ( G ) for the spectral radius of the neighbourhood first Zagreb matrix Υ ( G ) = [ δ ( i ) + δ ( j ) ] \Upsilon(G)=[\delta(i)+\delta(j)] Υ ( G ) = [ δ ( i ) + δ ( j )] of [24 ] . The estimate corresponding to Theorem 3.10 , namely 2 δ min ρ ( G ) ≤ ρ Υ ( G ) ≤ 2 δ max ρ ( G ) 2\delta_{\min}\rho(G)\le\rho_{\Upsilon}(G)\le2\delta_{\max}\rho(G) 2 δ m i n ρ ( G ) ≤ ρ Υ ( G ) ≤ 2 δ m a x ρ ( G ) , is [24 Theorem 6] , where equality is stated as holding if G G G is regular. Since 2 δ min A ( G ) ≤ Υ ( G ) ≤ 2 δ max A ( G ) 2\delta_{\min}A(G)\le\Upsilon(G)\le2\delta_{\max}A(G) 2 δ m i n A ( G ) ≤ Υ ( G ) ≤ 2 δ m a x A ( G ) entrywise, with equality on either side exactly when δ \delta δ is constant, Lemma 2.2 (a) and Lemma 3.1 show that equality in either inequality holds if and only if G G G is regular or bipartite semiregular, so that the bipartite semiregular graphs are extremal there as well.
Combining Lemma 3.2 and Theorem 3.10 we obtain the following bound, which depends on δ max \delta_{\max} δ m a x alone.
Corollary 3.12. Let G G G be a connected graph on n n n vertices. Then
ρ N F ( G ) ≤ δ max 2 δ max = δ max 5 / 2 , \rho_{NF}(G)\le\delta_{\max}^{2}\sqrt{\delta_{\max}}=\delta_{\max}^{5/2}, ρ N F ( G ) ≤ δ m a x 2 δ m a x = δ m a x 5/2 , and equality holds if and only if G G G is regular or bipartite semiregular.
Remark 3.13. Since δ max ≤ d max 2 \delta_{\max} \le d_{\max}^{2} δ m a x ≤ d m a x 2 , Corollary 3.12 implies ρ N F ( G ) ≤ δ max 5 / 2 ≤ d max 5 \rho_{NF}(G) \le\delta_{\max}^{5/2} \le d_{\max}^{5} ρ N F ( G ) ≤ δ m a x 5/2 ≤ d m a x 5 ; thus Corollary 3.12 is never weaker than Theorem 3.4 , and it is strictly stronger whenever δ max < d max 2 \delta_{\max} < d_{\max}^{2} δ m a x < d m a x 2 , i.e. whenever every vertex of maximum degree has a neighbour of degree less than d max d_{\max} d m a x . (Indeed δ ( i ) = d max 2 \delta(i) = d_{\max}^{2} δ ( i ) = d m a x 2 holds exactly when d ( i ) = d max d(i) = d_{\max} d ( i ) = d m a x and all neighbours of i i i have degree d max d_{\max} d m a x .)
Combining Theorem 3.10 with Hong’s inequality [17 ] and with Nikiforov’s inequality [27 , 28 ] gives bounds in terms of the order, the size, and the clique number. A complete regular ω \omega ω -partite graph is a complete ω \omega ω -partite graph K t , t , … , t K_{t,t,\ldots,t} K t , t , … , t whose ω \omega ω parts all have the same size t t t ; for t = 1 t = 1 t = 1 it is K ω K_{\omega} K ω .
Corollary 3.14 (part (i): [1 Cor. 3] ). Let G G G be a connected graph with n ≥ 2 n \ge2 n ≥ 2 vertices, m m m edges, and clique number ω \omega ω . Then
ρ N F ( G ) ≤ δ max 2 min { 2 m − n + 1 , 2 m ( 1 − 1 ω ) } . \rho_{NF}(G) \le\delta_{\max}^{2}\min\left\{\sqrt{2m-n+1},\sqrt{2m\left(1-\frac{1}{\omega}\right)}\right\}. ρ N F ( G ) ≤ δ m a x 2 min { 2 m − n + 1 , 2 m ( 1 − ω 1 ) } . More precisely:
(i) ρ N F ( G ) ≤ δ max 2 2 m − n + 1 \rho_{NF}(G) \le\delta_{\max}^{2}\sqrt{2m-n+1} ρ N F ( G ) ≤ δ m a x 2 2 m − n + 1 , with equality if and only if G ≅ K n G \cong K_n G ≅ K n or G ≅ K 1 , n − 1 G \cong K_{1,n-1} G ≅ K 1 , n − 1 ;
(ii) ρ N F ( G ) ≤ δ max 2 2 m ( 1 − 1 / ω ) \rho_{NF}(G) \le\delta_{\max}^{2}\sqrt{2m\left(1-1/\omega\right)} ρ N F ( G ) ≤ δ m a x 2 2 m ( 1 − 1/ ω ) , with equality if and only if G G G is a complete bipartite graph or a complete regular ω \omega ω -partite graph with ω ≥ 3 \omega\ge3 ω ≥ 3 .
Consequently, equality holds in the combined bound if and only if G G G is a complete bipartite graph or a complete regular multipartite graph.
Proof. (i) By Hong’s inequality, ρ ( G ) ≤ 2 m − n + 1 \rho(G) \le\sqrt{2m-n+1} ρ ( G ) ≤ 2 m − n + 1 for every connected graph, with equality if and only if G ≅ K n G \cong K_n G ≅ K n or G ≅ K 1 , n − 1 G \cong K_{1,n-1} G ≅ K 1 , n − 1 [17 ] ; combining this with Theorem 3.10 gives the bound. Equality requires equality in both estimates, that is, δ \delta δ constant together with G ≅ K n G \cong K_n G ≅ K n or G ≅ K 1 , n − 1 G \cong K_{1,n-1} G ≅ K 1 , n − 1 . Both graphs satisfy the former condition: δ ≡ ( n − 1 ) 2 \delta\equiv(n-1)^2 δ ≡ ( n − 1 ) 2 for K n K_n K n and δ ≡ n − 1 \delta\equiv n-1 δ ≡ n − 1 for K 1 , n − 1 K_{1,n-1} K 1 , n − 1 . Conversely, ρ N F ( K n ) = ( n − 1 ) 5 = ( n − 1 ) 4 n 2 − 2 n + 1 \rho_{NF}(K_n) = (n-1)^5 = (n-1)^4\sqrt{n^2-2n+1} ρ N F ( K n ) = ( n − 1 ) 5 = ( n − 1 ) 4 n 2 − 2 n + 1 and ρ N F ( K 1 , n − 1 ) = ( n − 1 ) 2 n − 1 \rho_{NF}(K_{1,n-1}) = (n-1)^2\sqrt{n-1} ρ N F ( K 1 , n − 1 ) = ( n − 1 ) 2 n − 1 by Proposition 2.8 , and in both cases the stated bound takes the same value.
(ii) By Nikiforov’s inequality [27 ] , ρ ( G ) ≤ 2 m ( 1 − 1 / ω ) \rho(G) \le\sqrt{2m(1-1/\omega)} ρ ( G ) ≤ 2 m ( 1 − 1/ ω ) for every graph with m m m edges and clique number ω \omega ω ; for a graph without isolated vertices, equality holds if and only if either ω = 2 \omega= 2 ω = 2 and G G G is complete bipartite, or ω ≥ 3 \omega\ge3 ω ≥ 3 and G G G is a complete regular ω \omega ω -partite graph [28 Theorem 2] . Combining this with Theorem 3.10 gives the bound. Equality requires equality in both estimates, that is, δ \delta δ constant together with one of the two structures just described. Both kinds of graphs have constant δ \delta δ : K p , q K_{p,q} K p , q is bipartite semiregular with δ ≡ p q \delta\equiv pq δ ≡ pq , and a complete regular ω \omega ω -partite graph is regular. Conversely, for K p , q K_{p,q} K p , q we have ω = 2 \omega= 2 ω = 2 , m = p q m = pq m = pq , δ max = p q \delta_{\max} = pq δ m a x = pq and ρ N F ( K p , q ) = ( p q ) 2 p q = δ max 2 m \rho_{NF}(K_{p,q}) = (pq)^2\sqrt{pq} = \delta_{\max}^{2}\sqrt{m} ρ N F ( K p , q ) = ( pq ) 2 pq = δ m a x 2 m ; for K t , … , t K_{t,\ldots,t} K t , … , t with ω ≥ 3 \omega\ge3 ω ≥ 3 parts the graph is r r r -regular with r = ( ω − 1 ) t r = (\omega-1)t r = ( ω − 1 ) t , so δ max = r 2 \delta_{\max} = r^2 δ m a x = r 2 , 2 m ( 1 − 1 / ω ) = ω t ⋅ r = r 2 2m(1-1/\omega) = \omega t\cdot r = r^2 2 m ( 1 − 1/ ω ) = ω t ⋅ r = r 2 and ρ N F ( G ) = r 5 = δ max 2 2 m ( 1 − 1 / ω ) \rho_{NF}(G) = r^5 = \delta_{\max}^{2}\sqrt{2m(1-1/\omega)} ρ N F ( G ) = r 5 = δ m a x 2 2 m ( 1 − 1/ ω ) by Proposition 2.8 (iv).
Finally, ρ N F ( G ) \rho_{NF}(G) ρ N F ( G ) is at most each of the two bounds, so it equals their minimum if and only if it equals one of them, i.e. if and only if equality holds in (i) or in (ii). Since K 2 K_2 K 2 and K 1 , n − 1 K_{1,n-1} K 1 , n − 1 are complete bipartite and K n K_n K n (n ≥ 3 n \ge3 n ≥ 3 ) is complete regular n n n -partite, the graphs in (i) already occur in (ii), and the combined equality case is that of (ii). □ \square □
Remark 3.15. The two estimates of Corollary 3.14 are not comparable. If G G G is bipartite, then ω = 2 \omega= 2 ω = 2 and 2 m ( 1 − 1 / ω ) = m ≤ 2 m − n + 1 2m(1-1/\omega) = m \le2m-n+1 2 m ( 1 − 1/ ω ) = m ≤ 2 m − n + 1 because m ≥ n − 1 m \ge n-1 m ≥ n − 1 , so (ii) is never weaker than (i), with equality exactly for trees; in this case (ii) also refines Theorem 4.2 , since δ max ≤ m \delta_{\max} \le m δ m a x ≤ m by Lemma 4.1 . For instance, for C 6 C_6 C 6 part (ii) gives 16 6 = 39.19 16\sqrt{6} = 39.19 16 6 = 39.19 and part (i) gives 16 7 = 42.33 16\sqrt{7} = 42.33 16 7 = 42.33 , while ρ N F ( C 6 ) = 32 \rho_{NF}(C_6) = 32 ρ N F ( C 6 ) = 32 ; for K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 part (ii) gives the exact value 1024 1024 1024 , whereas part (i) gives 1115.88 1115.88 1115.88 . In the other direction, for the triangle with one pendant edge (the graph S 4 + S_4^{+} S 4 + of § 5 ) one has n = m = 4 n = m = 4 n = m = 4 , ω = 3 \omega= 3 ω = 3 and 2 m − n + 1 = 5 < 16 3 = 2 m ( 1 − 1 / ω ) 2m-n+1 = 5 < \frac{16}{3} = 2m(1-1/\omega) 2 m − n + 1 = 5 < 3 16 = 2 m ( 1 − 1/ ω ) , so (i) is the better estimate: 25 5 = 55.90 25\sqrt{5} = 55.90 25 5 = 55.90 against 57.74 57.74 57.74 , with ρ N F ( S 4 + ) = 51.51 \rho_{NF}(S_4^{+}) = 51.51 ρ N F ( S 4 + ) = 51.51 .
Remark 3.16. The bound of Corollary 3.14(i) is [1 Corollary 3] , where equality is asserted only for K n K_n K n ; as shown above, the star attains it as well. The analogue of Corollary 3.14(i) for the matrix Υ ( G ) \Upsilon(G) Υ ( G ) is [24 Corollary 1] , where the upper bound 2 δ max 2 m − n + 1 2\delta_{\max}\sqrt{2m-n+1} 2 δ m a x 2 m − n + 1 is likewise asserted to be attained only by K n K_n K n . The star also attains it: for G = K 1 , n − 1 G=K_{1,n-1} G = K 1 , n − 1 one has δ ≡ n − 1 \delta\equiv n-1 δ ≡ n − 1 , hence ρ Υ ( G ) = 2 ( n − 1 ) ρ ( K 1 , n − 1 ) = 2 ( n − 1 ) n − 1 = 2 δ max 2 m − n + 1 \rho_{\Upsilon}(G)=2(n-1)\rho(K_{1,n-1})=2(n-1)\sqrt{n-1}=2\delta_{\max}\sqrt{2m-n+1} ρ Υ ( G ) = 2 ( n − 1 ) ρ ( K 1 , n − 1 ) = 2 ( n − 1 ) n − 1 = 2 δ m a x 2 m − n + 1 . The extremal graphs there are therefore K n K_n K n and K 1 , n − 1 K_{1,n-1} K 1 , n − 1 , in accordance with the equality condition in Hong’s inequality as quoted in [24 Lemma 4] .
The estimate of Theorem 3.10 can be improved by observing that only the weights carried by edges matter. This refinement is the key tool in § 5 .
Lemma 3.17. Let G G G be a connected graph and set
W ( G ) = max { i , j } ∈ E ( G ) δ ( i ) δ ( j ) , w ( G ) = min { i , j } ∈ E ( G ) δ ( i ) δ ( j ) . W(G)=\max_{\{i,j\}\in E(G)}\delta(i)\delta(j), \qquad w(G)=\min_{\{i,j\}\in E(G)}\delta(i)\delta(j). W ( G ) = { i , j } ∈ E ( G ) max δ ( i ) δ ( j ) , w ( G ) = { i , j } ∈ E ( G ) min δ ( i ) δ ( j ) . Then
W ( G ) ≤ ρ N F ( G ) and w ( G ) ρ ( G ) ≤ ρ N F ( G ) ≤ W ( G ) ρ ( G ) , W(G)\leq\rho_{N_F}(G) \qquad\text{and}\qquad w(G)\rho(G)\leq\rho_{N_F}(G)\leq W(G)\rho(G), W ( G ) ≤ ρ N F ( G ) and w ( G ) ρ ( G ) ≤ ρ N F ( G ) ≤ W ( G ) ρ ( G ) , and either of the last two inequalities is an equality if and only if G G G is regular or bipartite semiregular, in which case w ( G ) = W ( G ) = δ max 2 w(G)=W(G)=\delta_{\max}^{2} w ( G ) = W ( G ) = δ m a x 2 and both are equalities.
Proof. The ( i , j ) (i,j) ( i , j ) -th entry of N F ( G ) N_F(G) N F ( G ) equals δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) whenever i ∼ j i\sim j i ∼ j and 0 otherwise, so, entrywise,
w ( G ) A ( G ) ≤ N F ( G ) ≤ W ( G ) A ( G ) . w(G)A(G)\leq N_F(G)\leq W(G)A(G). w ( G ) A ( G ) ≤ N F ( G ) ≤ W ( G ) A ( G ) .
As G G G is connected, A ( G ) A(G) A ( G ) is irreducible, and Lemma 2.2 (a) gives w ( G ) ρ ( G ) ≤ ρ N F ( G ) ≤ W ( G ) ρ ( G ) w(G)\rho(G)\leq\rho_{N_F}(G)\leq W(G)\rho(G) w ( G ) ρ ( G ) ≤ ρ N F ( G ) ≤ W ( G ) ρ ( G ) , with equality on the right if and only if N F ( G ) = W ( G ) A ( G ) N_F(G)=W(G)A(G) N F ( G ) = W ( G ) A ( G ) and on the left if and only if N F ( G ) = w ( G ) A ( G ) N_F(G)=w(G)A(G) N F ( G ) = w ( G ) A ( G ) ; in either case δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) is constant on E ( G ) E(G) E ( G ) , so Lemma 3.3 applies. Conversely, if δ ≡ c \delta\equiv c δ ≡ c then N F ( G ) = c 2 A ( G ) N_F(G)=c^2A(G) N F ( G ) = c 2 A ( G ) and both inequalities are equalities.
For the first assertion, choose an edge { i , j } \{i,j\} { i , j } with δ ( i ) δ ( j ) = W ( G ) \delta(i)\delta(j)=W(G) δ ( i ) δ ( j ) = W ( G ) . The principal submatrix of N F ( G ) N_F(G) N F ( G ) indexed by { i , j } \{i,j\} { i , j } is
( 0 W ( G ) W ( G ) 0 ) , \begin{pmatrix} 0 & W(G) \\ W(G) & 0 \end{pmatrix}, ( 0 W ( G ) W ( G ) 0 ) ,
whose largest eigenvalue is W ( G ) W(G) W ( G ) ; now apply Lemma 2.3 .
Remark 3.18. Since w ( G ) ≥ δ min 2 w(G)\geq\delta_{\min}^{2} w ( G ) ≥ δ m i n 2 and W ( G ) ≤ δ max 2 W(G)\leq\delta_{\max}^{2} W ( G ) ≤ δ m a x 2 , Lemma 3.17 refines both bounds of Theorem 3.10 , and combined with Lemma 3.2 it refines Corollary 3.12. One has W ( G ) = δ max 2 W(G)=\delta_{\max}^{2} W ( G ) = δ m a x 2 if and only if some two adjacent vertices both attain δ max \delta_{\max} δ m a x , and w ( G ) = δ min 2 w(G)=\delta_{\min}^{2} w ( G ) = δ m i n 2 if and only if some two adjacent vertices both attain δ min \delta_{\min} δ m i n ; in all other cases the refinement is strict. For instance, for the graph S 6 + S_6^+ S 6 + of § 5 one has w = 35 > δ min 2 = 25 w=35>\delta_{\min}^{2}=25 w = 35 > δ m i n 2 = 25 and W = 49 W=49 W = 49 , and 49 ≤ ρ N F ( S 6 + ) = 110.83 ≤ W ρ ( G ) = 123.19 49\leq\rho_{N_F}(S_6^+)=110.83\leq W\rho(G)=123.19 49 ≤ ρ N F ( S 6 + ) = 110.83 ≤ W ρ ( G ) = 123.19 , while δ min 2 ρ ( G ) = 62.85 < w ρ ( G ) = 87.99 \delta_{\min}^{2}\rho(G)=62.85<w\rho(G)=87.99 δ m i n 2 ρ ( G ) = 62.85 < w ρ ( G ) = 87.99 .
Remark 3.19. By Lemma 6.2 and (11) below, ρ ( G ) 2 ≥ M 1 ( G ) / n ≥ δ min \rho(G)^2\geq M_1(G)/n\geq\delta_{\min} ρ ( G ) 2 ≥ M 1 ( G ) / n ≥ δ m i n , so Theorem 3.6 gives ρ N F ( G ) ≥ ρ ( G ) 5 ≥ δ min 2 ρ ( G ) \rho_{N_F}(G)\geq\rho(G)^5\geq\delta_{\min}^{2}\rho(G) ρ N F ( G ) ≥ ρ ( G ) 5 ≥ δ m i n 2 ρ ( G ) ; thus it is never weaker than the lower bound of Theorem 3.10 . It is, however, not comparable with the lower bound w ρ ( G ) w\rho(G) w ρ ( G ) of Lemma 3.17 . For S 6 + S_6^+ S 6 + one has ρ 5 = 100.45 > w ρ = 87.99 \rho^5=100.45>w\rho=87.99 ρ 5 = 100.45 > w ρ = 87.99 . On the other hand, let D ( k , k ) D(k,k) D ( k , k ) be the double star obtained by joining the centres of two copies of K 1 , k K_{1,k} K 1 , k by an edge; for D ( 5 , 5 ) D(5,5) D ( 5 , 5 ) one has w = 66 w=66 w = 66 , ρ = ( 1 + 21 ) / 2 \rho=(1+\sqrt{21})/2 ρ = ( 1 + 21 ) /2 , ρ 5 = 169.44 < w ρ = 184.22 \rho^5=169.44<w\rho=184.22 ρ 5 = 169.44 < w ρ = 184.22 , and ρ N F ( D ( 5 , 5 ) ) = 220 \rho_{N_F}(D(5,5))=220 ρ N F ( D ( 5 , 5 )) = 220 . Among the 995 connected graphs on 2 to 7 vertices, ρ 5 > w ρ \rho^5>w\rho ρ 5 > w ρ for 969 graphs, ρ 5 = w ρ \rho^5=w\rho ρ 5 = w ρ for the 24 regular or bipartite semiregular ones, and ρ 5 < w ρ \rho^5<w\rho ρ 5 < w ρ for the remaining 2.
Bipartite graphs and trees
Lemma 4.1. Let G G G be a connected bipartite graph with bipartition ( X , Y ) (X,Y) ( X , Y ) and m m m edges. Then δ max ≤ m \delta_{\max}\leq m δ m a x ≤ m . Moreover, for v ∈ V ( G ) v\in V(G) v ∈ V ( G ) we have δ ( v ) = m \delta(v)=m δ ( v ) = m if and only if v v v is adjacent to every vertex of the part not containing v v v .
Proof. Since G G G is bipartite, ∑ i ∈ X d ( i ) = ∑ j ∈ Y d ( j ) = m \sum_{i\in X}d(i)=\sum_{j\in Y}d(j)=m ∑ i ∈ X d ( i ) = ∑ j ∈ Y d ( j ) = m . If v ∈ X v\in X v ∈ X , then all neighbours of v v v lie in Y Y Y , whence δ ( v ) ≤ ∑ j ∈ Y d ( j ) = m \delta(v)\le\sum_{j\in Y}d(j)=m δ ( v ) ≤ ∑ j ∈ Y d ( j ) = m , with equality if and only if N G ( v ) = Y N_G(v)=Y N G ( v ) = Y . The other case is similar.
Theorem 4.2. Let G G G be a connected bipartite graph with m m m edges. Then
ρ N F ( G ) ≤ m 2 m , \rho_{\mathrm{NF}}(G)\le m^2\sqrt{m}, ρ NF ( G ) ≤ m 2 m , and equality holds if and only if G ≅ K p , q G\cong K_{p,q} G ≅ K p , q with p q = m pq=m pq = m .
Proof. By Corollary 3.12 and Lemma 4.1 , ρ N F ( G ) ≤ δ max 5 / 2 ≤ m 2 m \rho_{\mathrm{NF}}(G)\le\delta_{\max}^{5/2}\le m^2\sqrt{m} ρ NF ( G ) ≤ δ m a x 5/2 ≤ m 2 m . If equality holds, then equality holds in Corollary 3.12, so δ ≡ δ max \delta\equiv\delta_{\max} δ ≡ δ m a x , and moreover δ max = m \delta_{\max}=m δ m a x = m . Consequently, δ ( v ) = m \delta(v)=m δ ( v ) = m for every v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , and by Lemma 4.1 every vertex is adjacent to all vertices of the opposite part. Hence G ≅ K p , q G\cong K_{p,q} G ≅ K p , q with p = ∣ X ∣ p=|X| p = ∣ X ∣ , q = ∣ Y ∣ q=|Y| q = ∣ Y ∣ and p q = m pq=m pq = m . Conversely, ρ N F ( K p , q ) = ( p q ) 2 p q = m 2 m \rho_{\mathrm{NF}}(K_{p,q})=(pq)^2\sqrt{pq}=m^2\sqrt{m} ρ NF ( K p , q ) = ( pq ) 2 pq = m 2 m by Proposition 2.8 (ii).
To obtain a lower bound for trees, we need the following notation and two lemmas. For integers a , b , c ≥ 1 a,b,c\ge1 a , b , c ≥ 1 , let T ( a , b , c ) T(a,b,c) T ( a , b , c ) denote the tree with a vertex v v v such that T ( a , b , c ) − v T(a,b,c)-v T ( a , b , c ) − v consists of three paths on a a a , b b b and c c c vertices, each having an end vertex adjacent to v v v . Let H 7 H_7 H 7 denote the tree obtained from the path P 3 P_3 P 3 by attaching two pendant vertices to each of its two end vertices, and let D ( 2 , 2 ) D(2,2) D ( 2 , 2 ) be the double star of Remark 3.19. For a subgraph H H H of a graph G G G and i ∈ V ( H ) i\in V(H) i ∈ V ( H ) , let d H ( i ) d_H(i) d H ( i ) , δ H ( i ) \delta_H(i) δ H ( i ) and d G ( i ) d_G(i) d G ( i ) , δ G ( i ) \delta_G(i) δ G ( i ) denote the degree and the neighbourhood degree sum of i i i in H H H and in G G G .
Lemma 4.3. Let G G G be a connected graph and let H H H be a connected subgraph of G G G with at least two vertices. Then ρ N F ( H ) ≤ ρ N F ( G ) \rho_{\mathrm{NF}}(H)\le\rho_{\mathrm{NF}}(G) ρ NF ( H ) ≤ ρ NF ( G ) .
Proof. For every i ∈ V ( H ) i\in V(H) i ∈ V ( H ) we have N H ( i ) ⊆ N G ( i ) N_H(i)\subseteq N_G(i) N H ( i ) ⊆ N G ( i ) and d H ( j ) ≤ d G ( j ) d_H(j)\le d_G(j) d H ( j ) ≤ d G ( j ) for all j j j , and so δ H ( i ) ≤ δ G ( i ) \delta_H(i)\le\delta_G(i) δ H ( i ) ≤ δ G ( i ) . Hence N N F ( H ) ≤ N N F ( G ) [ V ( H ) ] N_{\mathrm{NF}}(H)\le N_{\mathrm{NF}}(G)[V(H)] N NF ( H ) ≤ N NF ( G ) [ V ( H )] entrywise. Since H H H is connected, the matrix N N F ( G ) [ V ( H ) ] N_{\mathrm{NF}}(G)[V(H)] N NF ( G ) [ V ( H )] is irreducible. By Lemma 2.2 (a) and Lemma 2.3 ,
ρ N F ( H ) ≤ ρ ( N N F ( G ) [ V ( H ) ] ) ≤ ρ N F ( G ) . \rho_{\mathrm{NF}}(H)\le\rho\left(N_{\mathrm{NF}}(G)[V(H)]\right)\le\rho_{\mathrm{NF}}(G). ρ NF ( H ) ≤ ρ ( N NF ( G ) [ V ( H )] ) ≤ ρ NF ( G ) .
Lemma 4.4.
(i) ρ N F ( P n ) < 32 \rho_{\mathrm{NF}}(P_n)<32 ρ NF ( P n ) < 32 for every n ≥ 2 n\ge2 n ≥ 2 .
(ii) Each of the trees K 1 , 4 K_{1,4} K 1 , 4 , T ( 1 , 2 , 2 ) T(1,2,2) T ( 1 , 2 , 2 ) , D ( 2 , 2 ) D(2,2) D ( 2 , 2 ) , H 7 H_7 H 7 and T ( 1 , 1 , 4 ) T(1,1,4) T ( 1 , 1 , 4 ) has ρ N F ≥ 32 \rho_{\mathrm{NF}}\ge32 ρ NF ≥ 32 .
Proof. (i) Every vertex of P n P_n P n has δ < 4 \delta<4 δ < 4 , and so N N F ( P n ) ≤ 16 A ( P n ) N_{\mathrm{NF}}(P_n)\le16A(P_n) N NF ( P n ) ≤ 16 A ( P n ) entrywise. Since ρ ( P n ) = 2 cos π n + 1 < 2 \rho(P_n)=2\cos\frac{\pi}{n+1}<2 ρ ( P n ) = 2 cos n + 1 π < 2 , Lemma 2.2 (a) gives ρ N F ( P n ) ≤ 16 ρ ( P n ) < 32 \rho_{\mathrm{NF}}(P_n)\le16\rho(P_n)<32 ρ NF ( P n ) ≤ 16 ρ ( P n ) < 32 .
(ii) We have ρ N F ( K 1 , 4 ) = 32 \rho_{\mathrm{NF}}(K_{1,4})=32 ρ NF ( K 1 , 4 ) = 32 by Proposition 2.8 (ii). For each of the other four trees, let z z z be the positive vector given below. Then N N F z ≥ 32 z N_{\mathrm{NF}}z\ge32z N NF z ≥ 32 z entrywise, so z T N N F z ≥ 32 z T z z^TN_{\mathrm{NF}}z\ge32z^Tz z T N NF z ≥ 32 z T z , and Lemma 2.1 gives ρ N F ≥ 32 \rho_{\mathrm{NF}}\ge32 ρ NF ≥ 32 .
(a) T ( 1 , 2 , 2 ) T(1,2,2) T ( 1 , 2 , 2 ) . The vertex of degree 3 has δ = 5 \delta=5 δ = 5 , its pendant neighbour has δ = 3 \delta=3 δ = 3 , the two vertices of degree 2 have δ = 4 \delta=4 δ = 4 , and the other two pendant vertices have δ = 2 \delta=2 δ = 2 . Let z z z take the values 20, 9, 13 and 3 at these vertices, respectively.
(b) D ( 2 , 2 ) D(2,2) D ( 2 , 2 ) . The two vertices of degree 3 have δ = 5 \delta=5 δ = 5 , and the pendant vertices have δ = 3 \delta=3 δ = 3 . Let z z z take the value 3 at the vertices of degree 3 and 1 at the pendant vertices.
(c) H 7 H_7 H 7 . The two vertices of degree 3 have δ = 4 \delta=4 δ = 4 , the vertex of degree 2 has δ = 6 \delta=6 δ = 6 , and the pendant vertices have δ = 3 \delta=3 δ = 3 . Let z z z take the values 4, 6 and 1 at these vertices, respectively. (d) T ( 1 , 1 , 4 ) T(1,1,4) T ( 1 , 1 , 4 ) . Let v v v be the vertex of degree 3 and let v p 1 p 2 p 3 p 4 vp_{1}p_{2}p_{3}p_{4} v p 1 p 2 p 3 p 4 be the path of length 4 starting at v v v . Then δ ( v ) = 4 \delta(v)=4 δ ( v ) = 4 , the two pendant neighbours of v v v have δ = 3 \delta=3 δ = 3 , and δ ( p 1 ) , δ ( p 2 ) , δ ( p 3 ) , δ ( p 4 ) \delta(p_{1}),\delta(p_{2}),\delta(p_{3}),\delta(p_{4}) δ ( p 1 ) , δ ( p 2 ) , δ ( p 3 ) , δ ( p 4 ) are 5 , 4 , 3 , 2 5,4,3,2 5 , 4 , 3 , 2 . Let z z z take the value 734 at v v v , the value 275 at the two pendant neighbours of v v v , and the values 845, 618, 240 and 45 at p 1 , p 2 , p 3 p_{1},p_{2},p_{3} p 1 , p 2 , p 3 and p 4 p_{4} p 4 .
Theorem 4.5. Let G G G be a tree on n ≥ 2 n \ge2 n ≥ 2 vertices. Then
ρ N F ( P n ) ≤ ρ N F ( G ) ≤ ( n − 1 ) 2 n − 1 . \rho_{NF}(P_n) \le\rho_{NF}(G) \le(n-1)^2\sqrt{n-1}. ρ N F ( P n ) ≤ ρ N F ( G ) ≤ ( n − 1 ) 2 n − 1 . Equality holds in the first inequality if and only if G ≅ P n G \cong P_n G ≅ P n , and in the second inequality if and only if G ≅ K 1 , n − 1 G \cong K_{1,n-1} G ≅ K 1 , n − 1 .
Proof. We first prove the upper bound. A tree on n n n vertices is bipartite and has m = n − 1 m=n-1 m = n − 1 edges, so Theorem 4.2 gives ρ N F ( G ) ≤ ( n − 1 ) 2 n − 1 \rho_{NF}(G) \le(n-1)^2\sqrt{n-1} ρ N F ( G ) ≤ ( n − 1 ) 2 n − 1 , with equality if and only if G ≅ K p , q G \cong K_{p,q} G ≅ K p , q where p q = n − 1 pq=n-1 pq = n − 1 and p + q = n p+q=n p + q = n . These two equations force { p , q } = { 1 , n − 1 } \{p,q\}=\{1,n-1\} { p , q } = { 1 , n − 1 } , i.e. G ≅ K 1 , n − 1 G \cong K_{1,n-1} G ≅ K 1 , n − 1 , and for the star equality indeed holds by Proposition 2.8 (ii).
Next we prove the lower bound. For n ≤ 3 n \le3 n ≤ 3 we have G ≅ P n G \cong P_n G ≅ P n . Let n ≥ 4 n \ge4 n ≥ 4 and suppose that G ≇ P n G \not\cong P_n G ≅ P n . Then G G G has a vertex v v v with d ( v ) ≥ 3 d(v) \ge3 d ( v ) ≥ 3 . We show that ρ N F ( G ) > ρ N F ( P n ) \rho_{NF}(G) > \rho_{NF}(P_n) ρ N F ( G ) > ρ N F ( P n ) , using Lemma 4.3 throughout.
Let n = 4 n=4 n = 4 . Then G ≅ K 1 , 3 G \cong K_{1,3} G ≅ K 1 , 3 , and ρ N F ( K 1 , 3 ) = 9 3 \rho_{NF}(K_{1,3})=9\sqrt{3} ρ N F ( K 1 , 3 ) = 9 3 by Proposition 2.8 (ii). The edge weights of N F ( P 4 ) N_F(P_4) N F ( P 4 ) are 6 , 9 , 6 6,9,6 6 , 9 , 6 , and for z = ( 1 , 2 , 2 , 1 ) T z=(1,2,2,1)^{T} z = ( 1 , 2 , 2 , 1 ) T we have N F ( P 4 ) z = 12 z N_F(P_4)z=12z N F ( P 4 ) z = 12 z . By Lemma 2.2 (c), ρ N F ( P 4 ) ≤ 12 < 9 3 \rho_{NF}(P_4)\le12<9\sqrt{3} ρ N F ( P 4 ) ≤ 12 < 9 3 .
Let n ∈ { 5 , 6 } n\in\{5,6\} n ∈ { 5 , 6 } . If d ( v ) ≥ 4 d(v)\ge4 d ( v ) ≥ 4 , then G G G contains K 1 , 4 K_{1,4} K 1 , 4 , and so ρ N F ( G ) ≥ 32 \rho_{NF}(G)\ge32 ρ N F ( G ) ≥ 32 . Otherwise d ( v ) = 3 d(v)=3 d ( v ) = 3 , and since n ≥ 5 n\ge5 n ≥ 5 , some neighbour of v v v has another neighbour. Hence G G G contains T ( 1 , 1 , 2 ) T(1,1,2) T ( 1 , 1 , 2 ) . In T ( 1 , 1 , 2 ) T(1,1,2) T ( 1 , 1 , 2 ) , the vertex of degree 3 has δ = 4 \delta=4 δ = 4 , its two pendant neighbours have δ = 3 \delta=3 δ = 3 , the vertex of degree 2 has δ = 4 \delta=4 δ = 4 , and the remaining pendant vertex has δ = 2 \delta=2 δ = 2 . The vector z z z taking the values 4, 2, 3 and 1 at these vertices satisfies N F ( T ( 1 , 1 , 2 ) ) z = 24 z N_F(T(1,1,2))z=24z N F ( T ( 1 , 1 , 2 )) z = 24 z , and so ρ N F ( G ) ≥ ρ N F ( T ( 1 , 1 , 2 ) ) ≥ 24 \rho_{NF}(G)\ge\rho_{NF}(T(1,1,2))\ge24 ρ N F ( G ) ≥ ρ N F ( T ( 1 , 1 , 2 )) ≥ 24 by Lemma 2.1 . On the other hand, the edge weights of N F ( P 6 ) N_F(P_6) N F ( P 6 ) are 6 , 12 , 16 , 12 , 6 6,12,16,12,6 6 , 12 , 16 , 12 , 6 , and for z = ( 1 , 3 , 5 , 5 , 3 , 1 ) T z=(1,3,5,5,3,1)^{T} z = ( 1 , 3 , 5 , 5 , 3 , 1 ) T we have N F ( P 6 ) z ≤ 23.2 z N_F(P_6)z\le23.2z N F ( P 6 ) z ≤ 23.2 z entrywise. By Lemma 2.2 (c), ρ N F ( P 5 ) ≤ ρ N F ( P 6 ) ≤ 23.2 < 24 \rho_{NF}(P_5)\le\rho_{NF}(P_6)\le23.2<24 ρ N F ( P 5 ) ≤ ρ N F ( P 6 ) ≤ 23.2 < 24 .
Let n ≥ 7 n\ge7 n ≥ 7 . By Lemma 4.4, it suffices to show that G G G contains one of the trees K 1 , 4 K_{1,4} K 1 , 4 , T ( 1 , 2 , 2 ) T(1,2,2) T ( 1 , 2 , 2 ) , D ( 2 , 2 ) D(2,2) D ( 2 , 2 ) , H 7 H_7 H 7 and T ( 1 , 1 , 4 ) T(1,1,4) T ( 1 , 1 , 4 ) , since then ρ N F ( G ) ≥ 32 > ρ N F ( P n ) \rho_{NF}(G)\ge32>\rho_{NF}(P_n) ρ N F ( G ) ≥ 32 > ρ N F ( P n ) . If d ( v ) ≥ 4 d(v)\ge4 d ( v ) ≥ 4 , then G G G contains K 1 , 4 K_{1,4} K 1 , 4 . So let the maximum degree of G G G be 3. If some vertex of degree 3 has two neighbours that are not pendant vertices, then G G G contains T ( 1 , 2 , 2 ) T(1,2,2) T ( 1 , 2 , 2 ) . If two vertices of degree 3 are adjacent, then G G G contains D ( 2 , 2 ) D(2,2) D ( 2 , 2 ) . Otherwise, since n ≥ 7 n\ge7 n ≥ 7 , every vertex of degree 3 is adjacent to exactly two pendant vertices, and no two vertices of degree 3 are adjacent. Deleting the pendant vertices adjacent to vertices of degree 3 gives a tree of maximum degree at most 2, that is, a path, and every vertex of degree 3 in G G G becomes an end vertex of this path. Hence G G G is obtained from a path by attaching two pendant vertices to one or to both of its end vertices. In the first case G G G contains T ( 1 , 1 , 4 ) T(1,1,4) T ( 1 , 1 , 4 ) , since n ≥ 7 n\ge7 n ≥ 7 . In the second case G ≅ H 7 G\cong H_7 G ≅ H 7 if n = 7 n=7 n = 7 , and G G G contains T ( 1 , 1 , 4 ) T(1,1,4) T ( 1 , 1 , 4 ) if n ≥ 8 n\ge8 n ≥ 8 . This completes the proof. □ \square □
Remark 4.6. Since m ≤ ⌊ n 2 / 4 ⌋ m\le\lfloor n^2/4\rfloor m ≤ ⌊ n 2 /4 ⌋ for a bipartite graph on n n n vertices, Theorem 4.2 gives ρ N F ( G ) ≤ ⌊ n 2 / 4 ⌋ 5 / 2 \rho_{NF}(G)\le\lfloor n^2/4\rfloor^{5/2} ρ N F ( G ) ≤ ⌊ n 2 /4 ⌋ 5/2 , with equality if and only if G ≅ K ⌊ n / 2 ⌋ , ⌈ n / 2 ⌉ G\cong K_{\lfloor n/2\rfloor,\lceil n/2\rceil} G ≅ K ⌊ n /2 ⌋ , ⌈ n /2 ⌉ . For even n n n this is [1 Theorem 8] . Theorem 4.2 also covers odd n n n , and being expressed in terms of m m m , is much sharper for sparse graphs: for K 1 , 9 K_{1,9} K 1 , 9 it gives the exact value 243, whereas [1 Theorem 8] gives 5 5 = 3125 5^5=3125 5 5 = 3125 . The analogue of the upper bound in Theorem 4.5 for γ ( G ) \gamma(G) γ ( G ) is [2 Lemma 21] , deduced there from [32 ] .
Remark 4.7. The proof shows that ρ N F ( G ) ≥ 32 \rho_{NF}(G)\ge32 ρ N F ( G ) ≥ 32 for every tree G ≇ P n G\not\cong P_n G ≅ P n on n ≥ 7 n\ge7 n ≥ 7 vertices, whereas ρ N F ( P n ) < 32 = ρ N F ( C n ) \rho_{NF}(P_n)<32=\rho_{NF}(C_n) ρ N F ( P n ) < 32 = ρ N F ( C n ) by Lemma 4.4(i). The bound in Lemma 4.4(i) is best possible. Indeed, let the vertices of P n P_n P n be 1 , 2 , … , n 1,2,\ldots,n 1 , 2 , … , n in order along the path. For n ≥ 6 n\ge6 n ≥ 6 the principal submatrix of N F ( P n ) N_F(P_n) N F ( P n ) indexed by the vertices 3 , 4 , … , n − 2 3,4,\ldots,n-2 3 , 4 , … , n − 2 is 16 A ( P n − 4 ) 16A(P_{n-4}) 16 A ( P n − 4 ) , and so Lemma 2.3 gives ρ N F ( P n ) ≥ 32 cos π n − 3 \rho_{NF}(P_n)\ge32\cos\frac{\pi}{n-3} ρ N F ( P n ) ≥ 32 cos n − 3 π , which tends to 32.
Unicyclic graphs
Let U n \mathcal{U}_n U n denote the set of connected unicyclic graphs on n ≥ 3 n \ge3 n ≥ 3 vertices. Let S n + S_n^+ S n + be the graph obtained from the star K 1 , n − 1 K_{1,n-1} K 1 , n − 1 by joining two of its pendant vertices by an edge. Equivalently, S n + S_n^+ S n + is obtained from the triangle C 3 C_3 C 3 by attaching n − 3 n-3 n − 3 pendant vertices to one of its vertices. In particular, S 3 + = C 3 S_3^+ = C_3 S 3 + = C 3 . In this section, we determine the minimum and the maximum of ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) over U n \mathcal{U}_n U n and characterise the graphs attaining them. For the adjacency spectral radius, C n C_n C n is the unique minimiser over U n \mathcal{U}_n U n and S n + S_n^+ S n + is the unique maximiser [4 , 29 ] ; see also [12 ] . Theorem 5.3 below is the analogue for N F ( G ) N_F(G) N F ( G ) . We first prove two lemmas.
Lemma 5.1. Let G G G be a connected graph and let v ∈ V ( G ) v \in V(G) v ∈ V ( G ) with N G ( v ) = { u , w 1 , … , w q } N_G(v) = \{u,w_1,\ldots,w_q\} N G ( v ) = { u , w 1 , … , w q } , where q ≥ 1 q \ge1 q ≥ 1 , each w i w_i w i is a pendant vertex and d ( u ) ≥ 2 d(u) \ge2 d ( u ) ≥ 2 . Let G ′ G' G ′ be obtained from G G G by replacing the edges { v , w i } \{v,w_i\} { v , w i } with { u , w i } \{u,w_i\} { u , w i } , 1 ≤ i ≤ q 1 \le i \le q 1 ≤ i ≤ q . Then ρ N F ( G ′ ) > ρ N F ( G ) \rho_{N_F}(G') > \rho_{N_F}(G) ρ N F ( G ′ ) > ρ N F ( G ) .
Proof. Let S = N G ( u ) ∖ { v } S = N_G(u) \setminus\{v\} S = N G ( u ) ∖ { v } , p = ∣ S ∣ ≥ 1 p = |S| \ge1 p = ∣ S ∣ ≥ 1 , and let δ ′ \delta' δ ′ denote the neighbourhood degree sum in G ′ G' G ′ . Since only the degrees of u u u and v v v change, we have
δ ′ ( u ) = δ ( u ) , δ ′ ( v ) = δ ( v ) = p + q + 1 , δ ′ ( w i ) = δ ( w i ) + p , \delta'(u) = \delta(u), \qquad\delta'(v) = \delta(v) = p+q+1, \qquad\delta'(w_i) = \delta(w_i)+p, δ ′ ( u ) = δ ( u ) , δ ′ ( v ) = δ ( v ) = p + q + 1 , δ ′ ( w i ) = δ ( w i ) + p ,
and δ ′ ( t ) ≥ δ ( t ) \delta'(t) \ge\delta(t) δ ′ ( t ) ≥ δ ( t ) for every other vertex t t t . Moreover, δ ( u ) − δ ( v ) = ∑ s ∈ S ( d ( s ) − 1 ) ≥ 0 \delta(u)-\delta(v) = \sum_{s \in S}(d(s)-1) \ge0 δ ( u ) − δ ( v ) = ∑ s ∈ S ( d ( s ) − 1 ) ≥ 0 .
Let X X X be the unit Perron vector of N F ( G ) N_F(G) N F ( G ) , and let Y Y Y be obtained from X X X by setting y u = max { x u , x v } y_u = \max\{x_u,x_v\} y u = max { x u , x v } and y v = min { x u , x v } y_v = \min\{x_u,x_v\} y v = min { x u , x v } . Then Y T Y = 1 Y^T Y = 1 Y T Y = 1 and y u y v = x u x v y_u y_v = x_u x_v y u y v = x u x v , so the edge { u , v } \{u,v\} { u , v } contributes equally to both quadratic forms below. By Lemma 2.1 ,
ρ N F ( G ′ ) − ρ N F ( G ) ≥ Y T N F ( G ′ ) Y − X T N F ( G ) X = 2 ∑ i = 1 q x w i ( δ ′ ( u ) δ ′ ( w i ) y u − δ ( v ) δ ( w i ) x v ) + 2 Σ , \rho_{N_F}(G')-\rho_{N_F}(G) \ge Y^T N_F(G')Y-X^T N_F(G)X = 2\sum_{i=1}^{q}x_{w_i}\bigl(\delta'(u)\delta'(w_i)y_u-\delta(v)\delta(w_i)x_v\bigr)+2\Sigma, ρ N F ( G ′ ) − ρ N F ( G ) ≥ Y T N F ( G ′ ) Y − X T N F ( G ) X = 2 i = 1 ∑ q x w i ( δ ′ ( u ) δ ′ ( w i ) y u − δ ( v ) δ ( w i ) x v ) + 2Σ ,
where Σ = ∑ ( δ ′ ( s ) δ ′ ( t ) y s y t − δ ( s ) δ ( t ) x s x t ) \Sigma=\sum\bigl(\delta'(s)\delta'(t)y_sy_t-\delta(s)\delta(t)x_sx_t\bigr) Σ = ∑ ( δ ′ ( s ) δ ′ ( t ) y s y t − δ ( s ) δ ( t ) x s x t ) and the sum is taken over the edges { s , t } ≠ { u , v } \{s,t\}\ne\{u,v\} { s , t } = { u , v } common to G G G and G ′ G' G ′ . Every term of Σ \Sigma Σ is nonnegative, since δ ′ ≥ δ \delta'\ge\delta δ ′ ≥ δ at the end vertices of these edges and y u ≥ x u y_u\ge x_u y u ≥ x u . Every term of the first sum is positive, since δ ( u ) ≥ δ ( v ) \delta(u)\ge\delta(v) δ ( u ) ≥ δ ( v ) , δ ′ ( w i ) > δ ( w i ) \delta'(w_i)>\delta(w_i) δ ′ ( w i ) > δ ( w i ) and y u ≥ x v > 0 y_u\ge x_v>0 y u ≥ x v > 0 . Hence ρ N F ( G ′ ) > ρ N F ( G ) \rho_{N_F}(G')>\rho_{N_F}(G) ρ N F ( G ′ ) > ρ N F ( G ) .
:::
Lemma 5.2. Let n ≥ 4 n \ge4 n ≥ 4 , r > 0 r>0 r > 0 and 3 ≤ g ≤ n 3 \le g \le n 3 ≤ g ≤ n , and let H H H be obtained from the cycle C g C_g C g by attaching n − g n-g n − g pendant vertices to vertices of C g C_g C g . Let B r ( H ) B_r(H) B r ( H ) be the matrix obtained from A ( H ) A(H) A ( H ) by replacing the entries corresponding to the pendant edges by r r r . Then
ρ ( B r ( H ) ) ≤ ρ ( B r ( S n + ) ) , \rho(B_r(H))\le\rho(B_r(S_n^+)), ρ ( B r ( H )) ≤ ρ ( B r ( S n + )) , with equality if and only if H ≅ S n + H\cong S_n^+ H ≅ S n + .
Proof. For t > 1 t>1 t > 1 , define
h ( t ) = t 2 − 2 t t − 1 = t 2 − 2 − 2 t − 1 . h(t)=t^2-\frac{2t}{t-1}=t^2-2-\frac{2}{t-1}. h ( t ) = t 2 − t − 1 2 t = t 2 − 2 − t − 1 2 .
Since h ′ ( t ) = 2 t + 2 / ( t − 1 ) 2 > 0 h'(t)=2t+2/(t-1)^2>0 h ′ ( t ) = 2 t + 2/ ( t − 1 ) 2 > 0 , the function h h h is strictly increasing on ( 1 , ∞ ) (1,\infty) ( 1 , ∞ ) . Let s = r 2 s=r^2 s = r 2 and Λ = ρ ( B r ( S n + ) ) \Lambda=\rho(B_r(S_n^+)) Λ = ρ ( B r ( S n + )) . Since A ( C 3 ) A(C_3) A ( C 3 ) is a principal submatrix of B r ( S n + ) B_r(S_n^+) B r ( S n + ) , Lemma 2.3 gives Λ ≥ 2 \Lambda\ge2 Λ ≥ 2 . Let z z z be the entry of the Perron vector of B r ( S n + ) B_r(S_n^+) B r ( S n + ) corresponding to the vertex of degree n − 1 n-1 n − 1 . By symmetry, the entries corresponding to the other two vertices of the triangle are z / ( Λ − 1 ) z/(\Lambda-1) z / ( Λ − 1 ) , and the entry corresponding to each pendant vertex is r z / Λ rz/\Lambda r z /Λ . The eigenvalue equation at the vertex of degree n − 1 n-1 n − 1 then gives
h ( Λ ) = ( n − 3 ) s . (6) h(\Lambda)=(n-3)s. \tag*{(6)} h ( Λ ) = ( n − 3 ) s . (6)
Now let λ = ρ ( B r ( H ) ) \lambda=\rho(B_r(H)) λ = ρ ( B r ( H )) . Since A ( C g ) A(C_g) A ( C g ) is a principal submatrix of B r ( H ) B_r(H) B r ( H ) , Lemma 2.3 gives λ ≥ 2 \lambda\ge2 λ ≥ 2 . Write C g = v 1 v 2 ⋯ v g v 1 C_g=v_1v_2\cdots v_gv_1 C g = v 1 v 2 ⋯ v g v 1 , let t i t_i t i be the number of pendant vertices adjacent to v i v_i v i , so that ∑ i = 1 g t i = n − g \sum_{i=1}^{g}t_i=n-g ∑ i = 1 g t i = n − g , and let x i x_i x i be the entry of the Perron vector of B r ( H ) B_r(H) B r ( H ) corresponding to v i v_i v i . Without loss of generality, we assume that x 1 = max i x i x_1=\max_i x_i x 1 = max i x i . The entry corresponding to a pendant vertex adjacent to v i v_i v i is r x i / λ r x_i/\lambda r x i / λ , and so the eigenvalue equation at v i v_i v i is
λ x i = x i − 1 + x i + 1 + s t i λ x i ( 1 ≤ i ≤ g ) . (7) \lambda x_i=x_{i-1}+x_{i+1}+\frac{s t_i}{\lambda}x_i \qquad(1\le i\le g). \tag*{(7)} λ x i = x i − 1 + x i + 1 + λ s t i x i ( 1 ≤ i ≤ g ) . (7)
with indices taken modulo g g g . Let S = x 1 + ⋯ + x g S=x_1+\cdots+x_g S = x 1 + ⋯ + x g . Summing (7) over all i i i , we obtain
( λ − 2 ) S = s λ ∑ i = 1 g t i x i ≤ ( n − g ) s λ x 1 . (8) (\lambda-2)S=\frac{s}{\lambda}\sum_{i=1}^{g}t_i x_i\le\frac{(n-g)s}{\lambda}x_1. \tag*{(8)} ( λ − 2 ) S = λ s i = 1 ∑ g t i x i ≤ λ ( n − g ) s x 1 . (8)
Summing (7) over i = 2 , … , g i=2,\ldots,g i = 2 , … , g and using x 2 + x g ≤ S − x 1 x_2+x_g\le S-x_1 x 2 + x g ≤ S − x 1 , we obtain
λ ( S − x 1 ) = 2 S − x 2 − x g + s λ ∑ i = 2 g t i x i ≥ S + x 1 , (9) \lambda(S-x_1)=2S-x_2-x_g+\frac{s}{\lambda}\sum_{i=2}^{g}t_i x_i\ge S+x_1, \tag*{(9)} λ ( S − x 1 ) = 2 S − x 2 − x g + λ s i = 2 ∑ g t i x i ≥ S + x 1 , (9)
that is, ( λ − 1 ) S ≥ ( λ + 1 ) x 1 (\lambda-1)S\ge(\lambda+1)x_1 ( λ − 1 ) S ≥ ( λ + 1 ) x 1 . Since λ ≥ 2 \lambda\ge2 λ ≥ 2 , (8) and (9) give
( λ − 2 ) ( λ + 1 ) λ − 1 x 1 ≤ ( λ − 2 ) S ≤ ( n − g ) s λ x 1 . \frac{(\lambda-2)(\lambda+1)}{\lambda-1}x_1\le(\lambda-2)S\le\frac{(n-g)s}{\lambda}x_1. λ − 1 ( λ − 2 ) ( λ + 1 ) x 1 ≤ ( λ − 2 ) S ≤ λ ( n − g ) s x 1 .
Multiplying by λ / x 1 \lambda/x_1 λ / x 1 and using λ ( λ − 2 ) ( λ + 1 ) / ( λ − 1 ) = h ( λ ) \lambda(\lambda-2)(\lambda+1)/(\lambda-1)=h(\lambda) λ ( λ − 2 ) ( λ + 1 ) / ( λ − 1 ) = h ( λ ) , we obtain
h ( λ ) ≤ ( n − g ) s ≤ ( n − 3 ) s . (10) h(\lambda)\le(n-g)s\le(n-3)s. \tag*{(10)} h ( λ ) ≤ ( n − g ) s ≤ ( n − 3 ) s . (10)
By (6) we have h ( λ ) ≤ h ( Λ ) h(\lambda)\le h(\Lambda) h ( λ ) ≤ h ( Λ ) , and since h h h is strictly increasing, λ ≤ Λ \lambda\le\Lambda λ ≤ Λ .
If λ = Λ \lambda=\Lambda λ = Λ , then equality holds throughout. Note that λ > 2 \lambda>2 λ > 2 , because h ( λ ) = ( n − 3 ) s > 0 = h ( 2 ) h(\lambda)=(n-3)s>0=h(2) h ( λ ) = ( n − 3 ) s > 0 = h ( 2 ) . Equality in (10) gives g = 3 g=3 g = 3 , and equality in (9) gives t i = 0 t_i=0 t i = 0 for i ≥ 2 i\ge2 i ≥ 2 . Thus all pendant vertices are adjacent to v 1 v_1 v 1 , and H ≅ S n + H\cong S_n^+ H ≅ S n + . Conversely, if H ≅ S n + H\cong S_n^+ H ≅ S n + , then ρ ( B r ( H ) ) = ρ ( B r ( S n + ) ) \rho(B_r(H))=\rho(B_r(S_n^+)) ρ ( B r ( H )) = ρ ( B r ( S n + )) .
We can now state the main result of this section.
Theorem 5.3. Let G G G be a connected unicyclic graph on n ≥ 3 n\ge3 n ≥ 3 vertices. Then
32 = ρ N F ( C n ) ≤ ρ N F ( G ) ≤ ρ N F ( S n + ) . 32=\rho_{NF}(C_n)\le\rho_{NF}(G)\le\rho_{NF}(S_n^+). 32 = ρ N F ( C n ) ≤ ρ N F ( G ) ≤ ρ N F ( S n + ) . Equality holds in the first inequality if and only if G ≅ C n G\cong C_n G ≅ C n , and in the second inequality if and only if G ≅ S n + G\cong S_n^+ G ≅ S n + .
Proof. We first prove the lower bound. Let C C C be the unique cycle of G G G and let g = ∣ V ( C ) ∣ g=|V(C)| g = ∣ V ( C ) ∣ . Every vertex of C C C has two neighbours on C C C , each of degree at least 2. Hence δ ( i ) ≥ 4 \delta(i)\ge4 δ ( i ) ≥ 4 for every i ∈ V ( C ) i\in V(C) i ∈ V ( C ) . Since G G G is unicyclic, C C C has no chords, so the edges of G G G with both end vertices in V ( C ) V(C) V ( C ) are exactly the g g g edges of C C C . Let X = ( x 1 , … , x n ) T X=(x_1,\ldots,x_n)^T X = ( x 1 , … , x n ) T with x i = 1 x_i=1 x i = 1 if i ∈ V ( C ) i\in V(C) i ∈ V ( C ) and x i = 0 x_i=0 x i = 0 otherwise. By Lemma 2.1,
ρ N F ( G ) ≥ X T N F ( G ) X X T X = 2 g ∑ { i , j } ∈ E ( C ) δ ( i ) δ ( j ) ≥ 2 g ⋅ 16 g = 32. \rho_{NF}(G)\ge\frac{X^T N_{F}(G)X}{X^T X}=\frac{2}{g}\sum_{\{i,j\}\in E(C)}\delta(i)\delta(j)\ge\frac{2}{g}\cdot16g=32. ρ N F ( G ) ≥ X T X X T N F ( G ) X = g 2 { i , j } ∈ E ( C ) ∑ δ ( i ) δ ( j ) ≥ g 2 ⋅ 16 g = 32.
Now suppose that G ≇ C n G\not\cong C_n G ≅ C n . Then g < n g<n g < n . Since G G G is connected, there exists a vertex i ∈ V ( C ) i\in V(C) i ∈ V ( C ) that has a neighbour outside C C C , and so d ( i ) ≥ 3 d(i)\ge3 d ( i ) ≥ 3 . As the two neighbours of i i i on C C C have degree at least 2, we have δ ( i ) ≥ 5 \delta(i)\ge5 δ ( i ) ≥ 5 . Consequently, δ ( i ) δ ( j ) ≥ 20 > 16 \delta(i)\delta(j)\ge20>16 δ ( i ) δ ( j ) ≥ 20 > 16 for each neighbour j j j of i i i on C C C , and the last inequality above is strict. Hence ρ N F ( G ) > 32 \rho_{NF}(G)>32 ρ N F ( G ) > 32 . Finally, ρ N F ( C n ) = 32 \rho_{NF}(C_n)=32 ρ N F ( C n ) = 32 by Proposition 2.8(iii). This proves the lower bound and its equality case.
Next we prove the upper bound. For n = 3 n=3 n = 3 we have G ≅ C 3 = S 3 + G\cong C_3=S_3^+ G ≅ C 3 = S 3 + . Let n ≥ 4 n\ge4 n ≥ 4 . Since U n \mathcal{U}_n U n is finite, we may choose a graph G 0 ∈ U n G_0\in\mathcal{U}_n G 0 ∈ U n with the maximum value of ρ N F \rho_{NF} ρ N F . Let C C C be the unique cycle of G 0 G_0 G 0 . We show that every vertex outside C C C is a pendant vertex. If not, let v v v be a non-pendant vertex outside C C C at maximum distance from C C C , and let u u u be the neighbour of v v v on a shortest path from v v v to C C C . Then all other neighbours of v v v are pendant vertices, and d ( u ) ≥ 2 d(u) \ge2 d ( u ) ≥ 2 . By Lemma 5.1 , moving these pendant vertices from v v v to u u u gives a graph in U n \mathcal{U}_n U n with a larger value of ρ N F \rho_{N_F} ρ N F , a contradiction. Hence G 0 G_0 G 0 is obtained from C C C by attaching pendant vertices to vertices of C C C .
Let a = n + 1 a=n+1 a = n + 1 and r = ( n − 1 ) / ( n + 1 ) r=(n-1)/(n+1) r = ( n − 1 ) / ( n + 1 ) . Since G 0 G_0 G 0 has n n n edges, ∑ j ∈ V ( G 0 ) d ( j ) = 2 n \sum_{j\in V(G_0)}d(j)=2n ∑ j ∈ V ( G 0 ) d ( j ) = 2 n , and so every vertex i i i of G 0 G_0 G 0 satisfies
δ ( i ) = n + 1 − ∑ j ∉ N G 0 [ i ] ( d ( j ) − 1 ) ≤ a . \delta(i)=n+1-\sum_{j\notin N_{G_0}[i]}(d(j)-1)\le a. δ ( i ) = n + 1 − j ∈ / N G 0 [ i ] ∑ ( d ( j ) − 1 ) ≤ a .
If i i i is a pendant vertex with neighbour k k k , then δ ( i ) = d ( k ) ≤ n − 1 = a r \delta(i)=d(k)\le n-1=ar δ ( i ) = d ( k ) ≤ n − 1 = a r . Hence δ ( i ) δ ( j ) ≤ a 2 \delta(i)\delta(j)\le a^2 δ ( i ) δ ( j ) ≤ a 2 on the edges of C C C and δ ( i ) δ ( j ) ≤ a 2 r \delta(i)\delta(j)\le a^2r δ ( i ) δ ( j ) ≤ a 2 r on the pendant edges, that is, N F ( G 0 ) ≤ a 2 B r ( G 0 ) N_F(G_0)\le a^2B_r(G_0) N F ( G 0 ) ≤ a 2 B r ( G 0 ) entrywise. In S n + S_n^+ S n + , the three vertices of the triangle have δ = n + 1 \delta=n+1 δ = n + 1 and the pendant vertices have δ = n − 1 \delta=n-1 δ = n − 1 , and so N F ( S n + ) = a 2 B r ( S n + ) N_F(S_n^+)=a^2B_r(S_n^+) N F ( S n + ) = a 2 B r ( S n + ) . By Lemma 2.2 (a) and Lemma 5.2 ,
ρ N F ( G 0 ) ≤ a 2 ρ ( B r ( G 0 ) ) ≤ a 2 ρ ( B r ( S n + ) ) = ρ N F ( S n + ) . \rho_{N_F}(G_0)\le a^2\rho(B_r(G_0))\le a^2\rho(B_r(S_n^+))=\rho_{N_F}(S_n^+). ρ N F ( G 0 ) ≤ a 2 ρ ( B r ( G 0 )) ≤ a 2 ρ ( B r ( S n + )) = ρ N F ( S n + ) .
By the choice of G 0 G_0 G 0 , equality holds throughout, and Lemma 5.2 gives G 0 ≅ S n + G_0\cong S_n^+ G 0 ≅ S n + . Thus S n + S_n^+ S n + is the unique graph in U n \mathcal{U}_n U n with the maximum value of ρ N F \rho_{N_F} ρ N F . Hence ρ N F ( G ) ≤ ρ N F ( S n + ) \rho_{N_F}(G)\le\rho_{N_F}(S_n^+) ρ N F ( G ) ≤ ρ N F ( S n + ) , with equality if and only if G ≅ S n + G\cong S_n^+ G ≅ S n + . This completes the proof.
Remark 5.4. For the neighbourhood first Zagreb matrix Υ ( G ) \Upsilon(G) Υ ( G ) , the analogue of Theorem 5.3 was proved in [2 Lemma 22] for n ≥ 7 n\ge7 n ≥ 7 by using the results of [32 ] on degree-based weighted adjacency matrices. These results do not apply to N F ( G ) N_F(G) N F ( G ) , since the weight δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) is not a function of d ( i ) d(i) d ( i ) and d ( j ) d(j) d ( j ) alone. Our proof uses the weights δ ( i ) δ ( j ) \delta(i)\delta(j) δ ( i ) δ ( j ) directly and holds for all n ≥ 3 n\ge3 n ≥ 3 .
Bounds involving the first Zagreb index
Recall that the first Zagreb index of G G G is M 1 ( G ) = ∑ i = 1 n d ( i ) 2 M_1(G)=\sum_{i=1}^{n}d(i)^2 M 1 ( G ) = ∑ i = 1 n d ( i ) 2 [14 ] . Counting the pairs (edge, incident vertex) in two ways gives the identity
∑ i = 1 n δ ( i ) = ∑ i = 1 n ∑ j ∼ i d ( j ) = ∑ j = 1 n d ( j ) 2 = M 1 ( G ) . (11) \sum_{i=1}^{n}\delta(i)=\sum_{i=1}^{n}\sum_{j\sim i}d(j)=\sum_{j=1}^{n}d(j)^2=M_1(G). \tag*{(11)} i = 1 ∑ n δ ( i ) = i = 1 ∑ n j ∼ i ∑ d ( j ) = j = 1 ∑ n d ( j ) 2 = M 1 ( G ) . (11)
Lemma 6.1. Let G G G be a connected graph on n ≥ 2 n\ge2 n ≥ 2 vertices. Then
δ max ≤ 1 2 M 1 ( G ) , \delta_{\max}\le\frac{1}{2}M_1(G), δ m a x ≤ 2 1 M 1 ( G ) , with equality if and only if G ≅ K 2 G\cong K_2 G ≅ K 2 .
Proof. Choose v ∈ V ( G ) v\in V(G) v ∈ V ( G ) with δ ( v ) = δ max \delta(v)=\delta_{\max} δ ( v ) = δ m a x . For every j ∼ v j\sim v j ∼ v we have
δ ( j ) = ∑ k ∼ j d ( k ) ≥ d ( v ) + ( d ( j ) − 1 ) , \delta(j)=\sum_{k\sim j}d(k)\ge d(v)+(d(j)-1), δ ( j ) = k ∼ j ∑ d ( k ) ≥ d ( v ) + ( d ( j ) − 1 ) ,
because the neighbour v v v contributes d ( v ) d(v) d ( v ) and each of the remaining d ( j ) − 1 d(j)-1 d ( j ) − 1 neighbours contributes at least 1. Summing over j ∼ v j\sim v j ∼ v ,
∑ j ∼ v δ ( j ) ≥ d ( v ) 2 + ∑ j ∼ v d ( j ) − d ( v ) = d ( v ) 2 − d ( v ) + δ ( v ) . \sum_{j\sim v}\delta(j)\ge d(v)^2+\sum_{j\sim v}d(j)-d(v)=d(v)^2-d(v)+\delta(v). j ∼ v ∑ δ ( j ) ≥ d ( v ) 2 + j ∼ v ∑ d ( j ) − d ( v ) = d ( v ) 2 − d ( v ) + δ ( v ) .
Hence, using (11) and δ ( i ) ≥ 1 \delta(i) \ge1 δ ( i ) ≥ 1 for all i i i ,
M 1 ( G ) = ∑ i = 1 n δ ( i ) ≥ δ ( v ) + ∑ j ∼ v δ ( j ) ≥ 2 δ ( v ) + d ( v ) ( d ( v ) − 1 ) ≥ 2 δ max . M_1(G)=\sum_{i=1}^{n}\delta(i)\ge\delta(v)+\sum_{j\sim v}\delta(j)\ge2\delta(v)+d(v)(d(v)-1)\ge2\delta_{\max}. M 1 ( G ) = i = 1 ∑ n δ ( i ) ≥ δ ( v ) + j ∼ v ∑ δ ( j ) ≥ 2 δ ( v ) + d ( v ) ( d ( v ) − 1 ) ≥ 2 δ m a x .
If equality holds, then d ( v ) ( d ( v ) − 1 ) = 0 d(v)(d(v)-1)=0 d ( v ) ( d ( v ) − 1 ) = 0 , so d ( v ) = 1 d(v)=1 d ( v ) = 1 ; moreover no vertex lies outside N G [ v ] N_G[v] N G [ v ] , since every vertex i i i has δ ( i ) ≥ 1 \delta(i)\ge1 δ ( i ) ≥ 1 . Thus V ( G ) = { v , j } V(G)=\{v,j\} V ( G ) = { v , j } where j j j is the unique neighbour of v v v , i.e. G ≅ K 2 G\cong K_2 G ≅ K 2 . Conversely, for K 2 K_2 K 2 we have δ max = 1 \delta_{\max}=1 δ m a x = 1 and M 1 = 2 M_1=2 M 1 = 2 .
For the lower bound we use the following classical estimate of Hofmeister [16 ] , whose short proof we include for completeness.
Lemma 6.2 ([16 ] ). Let G G G be a connected graph on n n n vertices. Then ρ ( G ) ≥ M 1 ( G ) / n \rho(G)\ge\sqrt{M_1(G)/n} ρ ( G ) ≥ M 1 ( G ) / n , with equality if and only if G G G is regular or bipartite semiregular.
Proof. Let 1 \mathbf{1} 1 be the all-ones vector. Since 1 T A ( G ) 2 1 = ∑ i ∑ j ∼ i d ( j ) = ∑ i δ ( i ) = M 1 ( G ) \mathbf{1}^{T}A(G)^2\mathbf{1}=\sum_i\sum_{j\sim i}d(j)=\sum_i\delta(i)=M_1(G) 1 T A ( G ) 2 1 = ∑ i ∑ j ∼ i d ( j ) = ∑ i δ ( i ) = M 1 ( G ) by (11) , the Rayleigh–Ritz inequality applied to A ( G ) 2 A(G)^2 A ( G ) 2 gives
ρ ( G ) 2 = λ max ( A ( G ) 2 ) ≥ 1 T A ( G ) 2 1 1 T 1 = M 1 ( G ) n . \rho(G)^2=\lambda_{\max}\left(A(G)^2\right)\ge\frac{\mathbf{1}^{T}A(G)^2\mathbf{1}}{\mathbf{1}^{T}\mathbf{1}}=\frac{M_1(G)}{n}. ρ ( G ) 2 = λ m a x ( A ( G ) 2 ) ≥ 1 T 1 1 T A ( G ) 2 1 = n M 1 ( G ) .
Equality holds if and only if 1 \mathbf{1} 1 is an eigenvector of A ( G ) 2 A(G)^2 A ( G ) 2 , that is, if and only if δ \delta δ is constant, which by Lemma 3.1 happens exactly when G G G is regular or bipartite semiregular.
Theorem 6.3. Let G G G be a connected graph on n ≥ 2 n\ge2 n ≥ 2 vertices. Then
ρ N F ( G ) ≥ w ( G ) M 1 ( G ) n ≥ δ min 2 M 1 ( G ) n . \rho_{NF}(G)\ge w(G)\sqrt{\frac{M_1(G)}{n}}\ge\delta_{\min}^{2}\sqrt{\frac{M_1(G)}{n}}. ρ N F ( G ) ≥ w ( G ) n M 1 ( G ) ≥ δ m i n 2 n M 1 ( G ) . and the first inequality is an equality if and only if G G G is regular or bipartite semiregular, in which case both are equalities.
Proof. Combine Lemma 3.17 with Lemma 6.2 ; the second inequality holds because w ( G ) ≥ δ min 2 w(G)\ge\delta_{\min}^{2} w ( G ) ≥ δ m i n 2 . Equality in the first estimate requires equality in both ingredients, and each of them holds precisely when δ \delta δ is constant (Lemmas 3.3 and 3.1 ); conversely, if δ ≡ c \delta\equiv c δ ≡ c then ρ N F ( G ) = c 2 ρ ( G ) = c 2 M 1 ( G ) / n \rho_{NF}(G)=c^2\rho(G)=c^2\sqrt{M_1(G)/n} ρ N F ( G ) = c 2 ρ ( G ) = c 2 M 1 ( G ) / n by Proposition 2.4 and Lemma 6.2 . Finally w ( G ) = δ min 2 w(G)=\delta_{\min}^{2} w ( G ) = δ m i n 2 exactly when some two adjacent vertices both attain δ min \delta_{\min} δ m i n , which is the case when δ \delta δ is constant.
The weaker estimate ρ N F ( G ) ≥ δ min 2 M 1 ( G ) / n \rho_{NF}(G)\ge\delta_{\min}^{2}\sqrt{M_1(G)/n} ρ N F ( G ) ≥ δ m i n 2 M 1 ( G ) / n is the lower bound of [1 Corollary 4] , where equality is asserted only for regular graphs; by Theorem 6.3 the bipartite semiregular graphs, for instance the stars, attain it as well. Theorem 3.6 gives a second lower bound in terms of M 1 M_1 M 1 .
Corollary 6.4. Let G G G be a connected graph on n ≥ 2 n\ge2 n ≥ 2 vertices. Then
ρ N F ( G ) ≥ ρ ( G ) 5 ≥ ( M 1 ( G ) n ) 5 / 2 , \rho_{NF}(G)\ge\rho(G)^5\ge\left(\frac{M_1(G)}{n}\right)^{5/2}, ρ N F ( G ) ≥ ρ ( G ) 5 ≥ ( n M 1 ( G ) ) 5/2 , and equality holds in either inequality if and only if G G G is regular or bipartite semiregular.
Proof. The first inequality and its equality case are Theorem 3.6 ; the second inequality and its equality case follow from Lemma 6.2 .
The bounds of Theorem 6.3 and Corollary 6.4 are not comparable. For S 6 + S_6^+ S 6 + one has ( M 1 / n ) 5 / 2 = 88.18 > w M 1 / n = 85.73 (M_1/n)^{5/2}=88.18>w\sqrt{M_1/n}=85.73 ( M 1 / n ) 5/2 = 88.18 > w M 1 / n = 85.73 , whereas for the double star D ( 5 , 5 ) D(5,5) D ( 5 , 5 ) of Remark 3.19 one has $(M_1/n)^{5/2}=122.06<w\sqrt{M_1/n}=172.53.
Bounds for the neighbourhood second Zagreb energy
In analogy with the graph energy of Gutman [13 ] , the neighbourhood second Zagreb energy of a graph G G G was defined in [1 ] as
E ( N F ) = ∑ i = 1 n ∣ λ i ∣ , \mathcal{E}(N_F)=\sum_{i=1}^{n}|\lambda_i|, E ( N F ) = i = 1 ∑ n ∣ λ i ∣ ,
where λ 1 ≥ ⋯ ≥ λ n \lambda_1\ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n are the eigenvalues of N F ( G ) N_F(G) N F ( G ) . Throughout this section G G G has no isolated vertices, T ( G ) T(G) T ( G ) is as in (2) and
P ( G ) = ∣ det N F ( G ) ∣ 2 / n = ( ∏ i = 1 n δ ( i ) ) 4 / n ∣ det A ( G ) ∣ 2 / n , P(G)=|\det N_F(G)|^{2/n}=\left(\prod_{i=1}^{n}\delta(i)\right)^{4/n}|\det A(G)|^{2/n}, P ( G ) = ∣ det N F ( G ) ∣ 2/ n = ( i = 1 ∏ n δ ( i ) ) 4/ n ∣ det A ( G ) ∣ 2/ n ,
the second expression being furnished by Proposition 2.5. We first record the estimate of McClelland type [23 ] , which follows from Lemma 2.7 and the Cauchy–Schwarz inequality:
E ( N F ) ≤ 2 n T ( G ) . (12) \mathcal{E}(N_F)\le\sqrt{2nT(G)}. \tag*{(12)} E ( N F ) ≤ 2 n T ( G ) . (12)
Theorem 7.1 ([1 Lemma 9] ). Let G G G be a graph on n n n vertices with no isolated vertices. Then
2 T ( G ) + n ( n − 1 ) P ( G ) ≤ E ( N F ) ≤ 2 ( n − 1 ) T ( G ) + n P ( G ) . \sqrt{2T(G)+n(n-1)P(G)}\le\mathcal{E}(N_F)\le\sqrt{2(n-1)T(G)+nP(G)}. 2 T ( G ) + n ( n − 1 ) P ( G ) ≤ E ( N F ) ≤ 2 ( n − 1 ) T ( G ) + n P ( G ) . Moreover, the upper bound never exceeds (12) , and it is strictly smaller unless every ∣ λ i ∣ |\lambda_i| ∣ λ i ∣ takes the same value, which for a graph without isolated vertices happens exactly when n n n is even and G ≅ n 2 K 2 G\cong\frac{n}{2}K_2 G ≅ 2 n K 2 .
Proof. For nonnegative real numbers a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n , Kober’s inequality [20 ] states
∑ i = 1 n a i + n ( n − 1 ) ( ∏ i = 1 n a i ) 1 / n ≤ ( ∑ i = 1 n a i ) 2 ≤ ( n − 1 ) ∑ i = 1 n a i + n ( ∏ i = 1 n a i ) 1 / n . \sum_{i=1}^{n}a_i+n(n-1)\left(\prod_{i=1}^{n}a_i\right)^{1/n}\le\left(\sum_{i=1}^{n}\sqrt{a_i}\right)^2\le(n-1)\sum_{i=1}^{n}a_i+n\left(\prod_{i=1}^{n}a_i\right)^{1/n}. i = 1 ∑ n a i + n ( n − 1 ) ( i = 1 ∏ n a i ) 1/ n ≤ ( i = 1 ∑ n a i ) 2 ≤ ( n − 1 ) i = 1 ∑ n a i + n ( i = 1 ∏ n a i ) 1/ n .
Take a i = λ i 2 a_i=\lambda_i^2 a i = λ i 2 . Then ∑ i a i = 2 T ( G ) \sum_i a_i=2T(G) ∑ i a i = 2 T ( G ) by Lemma 2.7, ∑ i a i = E ( N F ) \sum_i\sqrt{a_i}=\mathcal{E}(N_F) ∑ i a i = E ( N F ) and ( ∏ i a i ) 1 / n = ( ∏ i λ i 2 ) 1 / n = ∣ det N F ( G ) ∣ 2 / n = P ( G ) \left(\prod_i a_i\right)^{1/n}=\left(\prod_i\lambda_i^2\right)^{1/n}=|\det N_F(G)|^{2/n}=P(G) ( ∏ i a i ) 1/ n = ( ∏ i λ i 2 ) 1/ n = ∣ det N F ( G ) ∣ 2/ n = P ( G ) , which gives both inequalities.
By the arithmetic–geometric mean inequality, P ( G ) ≤ 1 n ∑ i λ i 2 = 2 T ( G ) n P(G)\le\frac{1}{n}\sum_i\lambda_i^2=\frac{2T(G)}{n} P ( G ) ≤ n 1 ∑ i λ i 2 = n 2 T ( G ) , whence 2 ( n − 1 ) T ( G ) + n P ( G ) ≤ 2 n T ( G ) 2(n-1)T(G)+nP(G)\le2nT(G) 2 ( n − 1 ) T ( G ) + n P ( G ) ≤ 2 n T ( G ) , with equality if and only if all λ i 2 \lambda_i^2 λ i 2 are equal. In that case N F ( G ) 2 = c 2 I n N_F(G)^2=c^2I_n N F ( G ) 2 = c 2 I n for some c > 0 c>0 c > 0 , so for i ≠ j i\ne j i = j we get 0 = ( N F 2 ) i j = ∑ k n i k n k j 0=(N_F^2)_{ij}=\sum_k n_{ik}n_{kj} 0 = ( N F 2 ) ij = ∑ k n ik n k j with all summands nonnegative, and therefore n i k n k j = 0 n_{ik}n_{kj}=0 n ik n k j = 0 for every k k k ; thus no two distinct vertices have a common neighbour, so every component of G G G has at most two vertices. As G G G has no isolated vertices, G ≅ n 2 K 2 G\cong\frac{n}{2}K_2 G ≅ 2 n K 2 , and conversely for this graph δ ≡ 1 \delta\equiv1 δ ≡ 1 , N F ( G ) = A ( G ) N_F(G)=A(G) N F ( G ) = A ( G ) and all ∣ λ i ∣ = 1 |\lambda_i|=1 ∣ λ i ∣ = 1 . □
The next bound is of Koolen–Moulton type [21 ] : it exploits any available lower estimate for ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) , and the sharper the estimate, the better the bound.
Theorem 7.2 (Koolen–Moulton type, cf. [21 ] ). Let G G G be a graph on n n n vertices with no isolated vertices, and let ρ 0 \rho_0 ρ 0 satisfy 2 T ( G ) / n ≤ ρ 0 ≤ ρ N F ( G ) \sqrt{2T(G)/n} \le\rho_0 \le\rho_{NF}(G) 2 T ( G ) / n ≤ ρ 0 ≤ ρ N F ( G ) . Then
E ( N F ) ≤ ρ 0 + ( n − 1 ) ( 2 T ( G ) − ρ 0 2 ) . \mathcal{E}(N_F) \le\rho_0+\sqrt{(n-1)(2T(G)-\rho_0^2)}. E ( N F ) ≤ ρ 0 + ( n − 1 ) ( 2 T ( G ) − ρ 0 2 ) . In particular, the choice
ρ 0 = max { 2 n M 2 ′ ( G ) , w ( G ) ρ ( G ) , W ( G ) , ρ ( G ) 5 , 2 T ( G ) / n } \rho_0=\max\left\{\frac{2}{n}M'_2(G),\ w(G)\rho(G),\ W(G),\ \rho(G)^5,\ \sqrt{2T(G)/n}\right\} ρ 0 = max { n 2 M 2 ′ ( G ) , w ( G ) ρ ( G ) , W ( G ) , ρ ( G ) 5 , 2 T ( G ) / n } is admissible when G G G is connected, and the resulting bound never exceeds (12) .
Proof. By the Cauchy–Schwarz inequality and Lemma 2.7 ,
E ( N F ) = ρ N F ( G ) + ∑ i = 2 n ∣ λ i ∣ ≤ ρ N F ( G ) + ( n − 1 ) ∑ i = 2 n λ i 2 = g ( ρ N F ( G ) ) , \mathcal{E}(N_F)=\rho_{NF}(G)+\sum_{i=2}^{n}|\lambda_i|\le\rho_{NF}(G)+\sqrt{(n-1)\sum_{i=2}^{n}\lambda_i^2}=g(\rho_{NF}(G)), E ( N F ) = ρ N F ( G ) + i = 2 ∑ n ∣ λ i ∣ ≤ ρ N F ( G ) + ( n − 1 ) i = 2 ∑ n λ i 2 = g ( ρ N F ( G )) ,
where g ( x ) = x + ( n − 1 ) ( 2 T ( G ) − x 2 ) g(x)=x+\sqrt{(n-1)(2T(G)-x^2)} g ( x ) = x + ( n − 1 ) ( 2 T ( G ) − x 2 ) . On the interval [ 2 T ( G ) / n , 2 T ( G ) ] [\sqrt{2T(G)/n},\sqrt{2T(G)}] [ 2 T ( G ) / n , 2 T ( G ) ] one has g ′ ( x ) = 1 − ( n − 1 ) x ( n − 1 ) ( 2 T ( G ) − x 2 ) ≤ 0 g'(x)=1-\frac{(n-1)x}{\sqrt{(n-1)(2T(G)-x^2)}}\le0 g ′ ( x ) = 1 − ( n − 1 ) ( 2 T ( G ) − x 2 ) ( n − 1 ) x ≤ 0 , so g g g is nonincreasing there. Since 2 T ( G ) = ∑ i λ i 2 ≤ n ρ N F ( G ) 2 2T(G)=\sum_i\lambda_i^2\le n\rho_{NF}(G)^2 2 T ( G ) = ∑ i λ i 2 ≤ n ρ N F ( G ) 2 we have ρ N F ( G ) ≥ 2 T ( G ) / n \rho_{NF}(G)\ge\sqrt{2T(G)/n} ρ N F ( G ) ≥ 2 T ( G ) / n , and ρ N F ( G ) ≤ 2 T ( G ) \rho_{NF}(G)\le\sqrt{2T(G)} ρ N F ( G ) ≤ 2 T ( G ) trivially; hence ρ 0 ≤ ρ N F ( G ) \rho_0\le\rho_{NF}(G) ρ 0 ≤ ρ N F ( G ) gives g ( ρ N F ( G ) ) ≤ g ( ρ 0 ) g(\rho_{NF}(G))\le g(\rho_0) g ( ρ N F ( G )) ≤ g ( ρ 0 ) , which is the asserted bound.
The five quantities listed are lower bounds for ρ N F ( G ) \rho_{NF}(G) ρ N F ( G ) : the first because the Rayleigh quotient at the all-ones vector equals 1 n 1 T N F ( G ) 1 = 2 n M 2 ′ ( G ) \frac{1}{n}\mathbf{1}^{T}N_F(G)\mathbf{1}=\frac{2}{n}M'_2(G) n 1 1 T N F ( G ) 1 = n 2 M 2 ′ ( G ) , the second and the third by Lemma 3.17 , the fourth by Theorem 3.6 , and the fifth as shown above. Finally g ( 2 T ( G ) / n ) = 2 T ( G ) / n + ( n − 1 ) 2 2 T ( G ) / n = 2 n T ( G ) g(\sqrt{2T(G)/n})=\sqrt{2T(G)/n}+\sqrt{(n-1)^2 2T(G)/n}=\sqrt{2nT(G)} g ( 2 T ( G ) / n ) = 2 T ( G ) / n + ( n − 1 ) 2 2 T ( G ) / n = 2 n T ( G ) , so the bound is never weaker than (12) .
Remark 7.3. The bound of Theorem 7.2 is attained by K n K_n K n : there δ ≡ ( n − 1 ) 2 \delta\equiv(n-1)^2 δ ≡ ( n − 1 ) 2 , 2 T = n ( n − 1 ) 9 2T=n(n-1)^9 2 T = n ( n − 1 ) 9 and ρ N F = ( n − 1 ) 5 = ρ 0 \rho_{NF}=(n-1)^5=\rho_0 ρ N F = ( n − 1 ) 5 = ρ 0 , so the right-hand side equals 2 ( n − 1 ) 5 = E ( N F ( K n ) ) 2(n-1)^5=\mathcal{E}(N_F(K_n)) 2 ( n − 1 ) 5 = E ( N F ( K n )) .
We now turn to lower bounds, where Proposition 2.5 yields complete characterisations of the extremal graphs.
Theorem 7.4. Let G G G be a graph on n n n vertices with no isolated vertices. Then
E ( N F ) ≥ 2 ρ N F ( G ) , \mathcal{E}(N_F)\ge2\rho_{NF}(G), E ( N F ) ≥ 2 ρ N F ( G ) , and E ( N F ) = 2 ρ N F ( G ) \mathcal{E}(N_F)=2\rho_{NF}(G) E ( N F ) = 2 ρ N F ( G ) if and only if G G G is a complete multipartite graph; in particular G G G is then connected, since a graph with two components containing edges has at least two positive N F N_F N F -eigenvalues. If G G G is connected, then moreover
2 ρ N F ( G ) ≥ 2 max { W ( G ) , w ( G ) ρ ( G ) , ρ ( G ) 5 } . 2\rho_{NF}(G)\ge2\max\{W(G),\ w(G)\rho(G),\ \rho(G)^5\}. 2 ρ N F ( G ) ≥ 2 max { W ( G ) , w ( G ) ρ ( G ) , ρ ( G ) 5 } .
Proof. By Lemma 2.7 the eigenvalues of N F ( G ) N_F(G) N F ( G ) sum to zero, so the positive ones and the negative ones have the same absolute total, giving E ( N F ) = 2 ∑ λ i > 0 λ i ≥ 2 λ 1 = 2 ρ N F ( G ) \mathcal{E}(N_F)=2\sum_{\lambda_i>0}\lambda_i\ge2\lambda_1=2\rho_{NF}(G) E ( N F ) = 2 ∑ λ i > 0 λ i ≥ 2 λ 1 = 2 ρ N F ( G ) , with equality if and only if N F ( G ) N_F(G) N F ( G ) has exactly one positive eigenvalue. By Proposition 2.5 this happens if and only if A ( G ) A(G) A ( G ) has exactly one positive eigenvalue, which by a theorem of Smith [30 ] characterises the complete multipartite graphs among graphs without isolated vertices; equivalently, by Corollary 2.6 (iii). The last inequality is Lemma 3.17 together with Theorem 3.6 .
Corollary 7.5. Let G G G be a connected unicyclic graph. Then E ( N F ) ≥ 64 \mathcal{E}(N_F)\ge64 E ( N F ) ≥ 64 , with equality if and only if G ≅ C 3 G\cong C_3 G ≅ C 3 or G ≅ C 4 G\cong C_4 G ≅ C 4 .
Proof. By Theorem 5.3 , ρ N F ( G ) ≥ 32 \rho_{NF}(G)\ge32 ρ N F ( G ) ≥ 32 , so E ( N F ) ≥ 64 \mathcal{E}(N_F)\ge64 E ( N F ) ≥ 64 by Theorem 7.4 . Equality requires ρ N F ( G ) = 32 \rho_{NF}(G)=32 ρ N F ( G ) = 32 , hence G ≅ C n G\cong C_n G ≅ C n by Theorem 5.3 , and simultaneously that G G G be complete multipartite; among the cycles only C 3 = K 1 , 1 , 1 C_3=K_{1,1,1} C 3 = K 1 , 1 , 1 and C 4 = K 2 , 2 C_4=K_{2,2} C 4 = K 2 , 2 are complete multipartite. For both, N F ( G ) = 16 A ( G ) N_F(G)=16A(G) N F ( G ) = 16 A ( G ) and E ( N F ) = 16 E ( G ) = 64 \mathcal{E}(N_F)=16\mathcal{E}(G)=64 E ( N F ) = 16 E ( G ) = 64 .
Theorem 7.6. Let G G G be a connected graph on n n n vertices. Then
E ( N F ) ≥ 2 T ( G ) ρ N F ( G ) ≥ 2 T ( G ) W ( G ) ρ ( G ) ≥ 2 T ( G ) δ max 5 / 2 , \mathcal{E}(N_F) \ge\frac{2T(G)}{\rho_{N_F}(G)} \ge\frac{2T(G)}{W(G)\rho(G)} \ge\frac{2T(G)}{\delta_{\max}^{5/2}}, E ( N F ) ≥ ρ N F ( G ) 2 T ( G ) ≥ W ( G ) ρ ( G ) 2 T ( G ) ≥ δ m a x 5/2 2 T ( G ) , and the first inequality is an equality if and only if G G G is a complete bipartite graph.
Proof. By Lemma 2.7 ,
2 T ( G ) = ∑ i = 1 n λ i 2 = ∑ i = 1 n ∣ λ i ∣ ∣ λ i ∣ ≤ ρ N F ( G ) ∑ i = 1 n ∣ λ i ∣ = ρ N F ( G ) E ( N F ) , 2T(G)=\sum_{i=1}^{n}\lambda_i^2=\sum_{i=1}^{n}|\lambda_i||\lambda_i|\leq\rho_{N_F}(G)\sum_{i=1}^{n}|\lambda_i|=\rho_{N_F}(G)\mathcal{E}(N_F), 2 T ( G ) = i = 1 ∑ n λ i 2 = i = 1 ∑ n ∣ λ i ∣∣ λ i ∣ ≤ ρ N F ( G ) i = 1 ∑ n ∣ λ i ∣ = ρ N F ( G ) E ( N F ) ,
which gives the first inequality. The second follows from Lemma 3.17 , and the third from W ( G ) ≤ δ max 2 W(G)\leq\delta_{\max}^2 W ( G ) ≤ δ m a x 2 together with ρ ( G ) ≤ δ max \rho(G)\leq\sqrt{\delta_{\max}} ρ ( G ) ≤ δ m a x (Lemma 3.2 ), which give W ( G ) ρ ( G ) ≤ δ max 5 / 2 W(G)\rho(G)\leq\delta_{\max}^{5/2} W ( G ) ρ ( G ) ≤ δ m a x 5/2 . Equality in the displayed estimate holds if and only if ∣ λ i ∣ ( ρ N F ( G ) − ∣ λ i ∣ ) = 0 |\lambda_i|(\rho_{N_F}(G)-|\lambda_i|)=0 ∣ λ i ∣ ( ρ N F ( G ) − ∣ λ i ∣ ) = 0 for every i i i , that is, if and only if every eigenvalue of N F ( G ) N_F(G) N F ( G ) lies in { ρ N F ( G ) , 0 , − ρ N F ( G ) } \{\rho_{N_F}(G),0,-\rho_{N_F}(G)\} { ρ N F ( G ) , 0 , − ρ N F ( G )} . As G G G is connected, N F ( G ) N_F(G) N F ( G ) is irreducible and ρ N F ( G ) \rho_{N_F}(G) ρ N F ( G ) is a simple eigenvalue; since the eigenvalues sum to zero, − ρ N F ( G ) -\rho_{N_F}(G) − ρ N F ( G ) then occurs exactly once as well, so rank N F ( G ) = 2 \operatorname{rank}N_F(G)=2 rank N F ( G ) = 2 . By Proposition 2.5 , rank A ( G ) = 2 \operatorname{rank}A(G)=2 rank A ( G ) = 2 , so G ≅ K p , q G\cong K_{p,q} G ≅ K p , q by Corollary 2.6 (ii). Conversely, for G = K p , q G=K_{p,q} G = K p , q we have N F ( G ) = ( p q ) 2 A ( G ) N_F(G)=(pq)^2A(G) N F ( G ) = ( pq ) 2 A ( G ) , whence E ( N F ) = 2 ( p q ) 5 / 2 \mathcal{E}(N_F)=2(pq)^{5/2} E ( N F ) = 2 ( pq ) 5/2 , ρ N F ( G ) = ( p q ) 5 / 2 \rho_{N_F}(G)=(pq)^{5/2} ρ N F ( G ) = ( pq ) 5/2 and T ( G ) = ( p q ) 5 T(G)=(pq)^5 T ( G ) = ( pq ) 5 , so equality holds.
Acknowledgments
The second author acknowledges financial support from the ANRF-CRG grant (File Number: CRG/2023/002747). The authors acknowledge the use of AI-Claude for improving the exposition of the manuscript and refining some of the proofs. All mathematical statements have been independently verified by the authors, who are solely responsible for the correctness of the results presented in this paper.
Declarations
Conflict of interest: The authors declare that they have no competing interests.