betaFeedback

WorksMathematics

Neighbourhood second Zagreb matrix of graphs: spectral radius bounds and extremal graphs

Abstract

Let GG be a connected graph on at least two vertices, and let δ(i)δ(i) be the sum of the degrees of the neighbours of a vertex ii. The neighbourhood second Zagreb matrix \NF(G) has (i,j)(i,j)-entry δ(i)δ(j)δ(i)δ(j) if i∼ji\sim j and 00 otherwise; its spectral radius is denoted by \rNF(G). We prove that \rNF(G)\geρ(G)^{5}, where ρ(G)ρ(G) is the adjacency spectral radius, with equality if and only if GG is regular or bipartite semiregular, and we use this to show that the same graphs are exactly the extremal graphs of a Berman–Zhang–type upper bound. We sharpen the estimates \demin^{2}ρ(G)\le\rNF(G)\le\demax^{2}ρ(G) by means of the extreme edge weights of \NF(G), give sharp upper bounds in terms of the maximum degree \dmax, the maximum neighbourhood degree sum \demax, the size mm and the clique number ω(G)ω(G), and determine the extremal graphs for bipartite graphs and trees. For every connected unicyclic graph GG of order n≥3n\ge3 we prove 32=\rNF(C_n)\le\rNF(G)\le\rNF(\Sp n), where \Sp n is the triangle with n−3n-3 pendant edges at one vertex, with equality only for CnC_n and only for \Sp n, respectively. Finally, we give bounds in terms of the first Zagreb index and for the neighbourhood second Zagreb energy; for lower energy bounds, the extremal graphs are described completely.

Introduction

All graphs considered here are finite, simple, and undirected. Let GG be a graph with vertex set V(G)={1,2,…,n}V(G)=\{1,2,\ldots,n\} and edge set E(G)E(G), ∣E(G)∣=m|E(G)|=m. If two vertices ii and jj are adjacent, we write i∼ji\sim j and denote the corresponding edge by {i,j}\{i,j\}. The adjacency matrix of GG is A(G)=[aij]A(G)=[a_{ij}], where aij=1a_{ij}=1 if i∼ji\sim j and aij=0a_{ij}=0 otherwise. Since A(G)A(G) is real and symmetric, its eigenvalues μ1≥μ2≥⋯≥μn\mu_1\geq\mu_2\geq\cdots\geq\mu_n are real; the largest one, μ1(G)\mu_1(G), is the spectral radius of GG and is denoted by ρ(G)\rho(G).

For i∈V(G)i\in V(G) let NG(i)N_G(i) be the neighbourhood of ii, NG[i]=NG(i)∪{i}N_G[i]=N_G(i)\cup\{i\} its closed neighbourhood and d(i)=∣NG(i)∣d(i)=|N_G(i)| its degree. Following the standard terminology of chemical graph theory, the neighbourhood degree sum of ii is

δ(i)=∑j∼id(j).\delta(i)=\sum_{j\sim 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)\} and δmin⁡=δmin⁡(G)=min⁡{δ(i):i∈V(G)}\delta_{\min}=\delta_{\min}(G)=\min\{\delta(i):i\in V(G)\}, and similarly dmax⁡,dmin⁡d_{\max},d_{\min} for the maximum and minimum degree. Clearly

dmin⁡2≤δmin⁡≤δmax⁡≤dmax⁡2.(1)d_{\min}^{2}\leq\delta_{\min}\leq\delta_{\max}\leq d_{\max}^{2}. \tag*{(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) is replaced by δ(i)\delta(i), have attracted considerable attention [25, 26]. Ghorbani and Hosseinzadeh [11] introduced the neighbourhood first and second Zagreb indices

M1′(G)=∑{i,j}∈E(G)(δ(i)+δ(j)),M2′(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).

The index M2′M'_2 also appears as M2∗M^*_2 [25] and as NM2NM_2 in the literature. Note that MN(G)=∑vδ(v)2M_N(G)=\sum_v\delta(v)^2 of [25, 26] differs from MN′(G)=∑vd(v)δ(v)M'_N(G)=\sum_v d(v)\delta(v). We use the index M2′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 FF, the associated weighted adjacency matrix AF(G)A_F(G) has (i,j)(i,j)-th entry F(d(i),d(j))F(d(i),d(j)) if i∼ji\sim j and 00 otherwise [8]; the extremal theory of ρ(AF)\rho(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 FF. Jafari Rad, Jahanbani and Gutman [19] considered in particular the first and second Zagreb matrices, whose (i,j)(i,j)-th entries are d(i)+d(j)d(i)+d(j) and d(i)d(j)d(i)d(j) on the edges of GG; Mondal et al. [24] replaced d(i)d(i) by δ(i)\delta(i) in the additive case, studied the energy of the resulting neighbourhood first Zagreb matrix Υ(G)=[δ(i)+δ(j)]\Upsilon(G)=[\delta(i)+\delta(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 GG, denoted by NF(G)N_F(G) (or simply NFN_F), is the n×nn\times n matrix NF(G)=[nij]N_F(G)=[n_{ij}] defined by

nij={δ(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}

The matrix NF(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, and λ1\lambda_1 is called the neighbourhood second Zagreb spectral radius of GG, written ρNF(G)\rho_{N_F}(G). Note that the sum of the entries of NF(G)N_F(G) above the diagonal is precisely M2′(G)M'_2(G), so that NF(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) to NF(G)N_F(G) amounts to weighting each contact by the product of the neighbourhood degrees of its endpoints, so that ρNF(G)\rho_{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 ρNF(G)\rho_{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 ρNF(G)\rho_{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 NFN_F-based descriptors, in the manner of [24], would be a natural complement to the present work.

In [1], sharp bounds for ρNF(G)\rho_{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 ρNF(G)\rho_{N_F}(G). Lemma 3.17 replaces the factor δmax⁡2\delta_{\max}^2 in the classical comparison ρNF(G)≤δmax⁡2ρ(G)\rho_{N_F}(G)\le\delta_{\max}^2\rho(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). Theorem 3.6 proves that ρNF(G)≥ρ(G)5\rho_{N_F}(G)\ge\rho(G)^5, which is never weaker than the lower estimate δmin⁡2ρ(G)\delta_{\min}^2\rho(G), and strictly better unless GG 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) 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 CnC_n is the unique minimiser of ρNF\rho_{NF} on Un\mathcal{U}_n and that the triangle with n−3n-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 NF(G)N_F(G) in [1], for the additive matrix Υ(G)\Upsilon(G) in [2, 24], or for the adjacency matrix itself, we state result by result what the present paper contributes. Table 1 summarises this.

References

  1. [1]S. Barik and P. Verma, On spectral properties of neighborhood second Zagreb matrix of graphs, Commun. Comb. Optim. 10 (2025), no. 2, 275–293. https://doi.org/10.22049/cco.2023.28424.1546
  2. [2]S. Barik and P. Verma, On the neighborhood first Zagreb spectral radius and the neighborhood first Zagreb energy of graphs, AKCE Int. J. Graphs Comb., accepted (2024).
  3. [3]A. Berman and X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001), 233–240.DOI
  4. [4]R. A. Brualdi and E. S. Solheid, On the spectral radius of complementary acyclic matrices of zeros and ones, SIAM J. Algebraic Discrete Methods 7 (1986), 265–272.DOI
  5. [5]D. S. Cao, Bounds on the eigenvalues and chromatic number, Linear Algebra Appl. 270 (1998), 1–13.
  6. [6]B. Cheng and B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007), 60–67.
  7. [7]D. Cvetkovic, P. Rowlinson and S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010.DOI
  8. [8]K. C. Das, I. Gutman, I. Milovanovic, E. Milovanovic and B. Furtula, Degree-based energies of graphs, Linear Algebra Appl. 554 (2018), 185–204.DOI
  9. [9]O. Favaron, M. Maheo and J.-F. Sacle, Some eigenvalue properties in graphs (conjectures of Graffiti II), Discrete Math. 111 (1993), 197–220.DOI
  10. [10]B. Furtula and I. Gutman, A forgotten topological index, J. Math. Chem. 53 (2015), 1184–1190.DOI
  11. [11]M. Ghorbani and M. A. Hosseinzadeh, A note on Zagreb indices of nanostar dendrimers, Optoelectron. Adv. Mater. Rapid Comm. 4 (2010), 1877–1880.
  12. [12]S. G. Guo, The spectral radius of unicyclic and bicyclic graphs with n vertices and k pendant vertices, Linear Algebra Appl. 408 (2005), 78–85.DOI
  13. [13]I. Gutman, The energy of a graph, Ber. Math.-Statist. Sekt. Forschungsz. Graz 103 (1978), 1–22.
  14. [14]I. Gutman and N. Trinajstic, Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972), 535–538.DOI
  15. [15]I. Gutman, B. Rusčić, N. Trinajstic and C. F. Wilcox, Graph theory and molecular orbitals. XII. Acyclic polyenes, J. Chem. Phys. 62 (1975), 3399–3405.DOI
  16. [16]M. Hofmeister, Spectral radius and degree sequence, Math. Nachr. 139 (1988), 37–44.DOI
  17. [17]Y. Hong, A bound on the spectral radius of graphs, Linear Algebra Appl. 108 (1988), 135–139.DOI
  18. [18]R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, 2013.
  19. [19]N. Jafari Rad, A. Jahanbani and I. Gutman, Zagreb energy and Zagreb Estrada index of graphs, MATCH Commun. Math. Comput. Chem. 79 (2018), 371–386.
  20. [20]H. Kober, On the arithmetic and geometric means and on Hölder’s inequality, Proc. Amer. Math. Soc. 9 (1958), 452–459.
  21. [21]J. H. Koolen and V. Moulton, Maximal energy graphs, Adv. Appl. Math. 26 (2001), 47–52.DOI
  22. [22]X. Li and Z. Wang, Trees with extremal spectral radius of weighted adjacency matrices among trees weighted by degree-based indices, Linear Algebra Appl. 620 (2021), 61–75.DOI
  23. [23]B. J. McClelland, Properties of the latent roots of a matrix: the estimation of π-electron energies, J. Chem. Phys. 54 (1971), 640–643.DOI
  24. [24]S. Mondal, S. Barik, N. De and A. Pal, A note on neighborhood first Zagreb energy and its significance as a molecular descriptor, Chemometr. Intell. Lab. Syst. 222 (2022), Article ID 104494.DOI
  25. [25]S. Mondal, N. De and A. Pal, On some new neighborhood degree based indices, Acta Chem. Iasi 27 (2019), 31–46.arxiv.org/abs/1906.11215
  26. [26]S. Mondal, N. De and A. Pal, On neighborhood Zagreb index of product graphs, J. Mol. Struct. 1223 (2021), 129210.DOI
  27. [27]V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002), 179–189.DOI
  28. [28]V. Nikiforov, More spectral bounds on the clique and independence numbers, J. Combin. Theory Ser. B 99 (2009), 819–826.arxiv.org/abs/0706.0548
  29. [29]S. K. Simić, On the largest eigenvalue of unicyclic graphs, Publ. Inst. Math. (Beograd) 42 (1987), 13–19.
  30. [30]J. H. Smith, Some properties of the spectrum of a graph, in: Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, pp. 403–406.
  31. [31]P. Van Mieghem, J. Omic and R. Kooij, Virus spread in networks, IEEE/ACM Trans. Netw. 17 (2009), no. 1, 1–14.
  32. [32]R. Zheng, X. Guan and X. Jin, Extremal trees and unicyclic graphs with respect to spectral radius of weighted adjacency matrices with property P*, J. Appl. Math. Comput. 69 (2023), no. 3, 2573–2594.DOI

Paper details

vlnc:W_epnqkbps
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI-Claude

View statement
Looking for related papers…
Contents