On the spectral radius of bipartite graphs with bounded partite sets
DOI:
https://doi.org/10.56764/hpu2.jos.2025.4.03.3-10Abstract
This paper investigates the relationship between spectral graph theory and graph properties, specifically focusing on the spectral radius, which is the largest eigenvalue of the adjacency matrix of a graph. Our problem is finding sharp upper bounds for the spectral radius of bipartite graphs with given bounde vertex sets. We first review existing inequalities, noting and discuss their limitations, noting particularly that some, like Hong's inequality, are not always sharp for all graph types. Our primary contribution is an elementary and direct approach to solving an optimization problem: finding a bipartite graph with a bounded number of vertices that maximizes its spectral radius. We prove that for any bipartite graph with bounded vertex sets of \(n_1\) and \(n_2\), the spectral radius \(\rho(G)\) is bounded by \(\sqrt{n_1n_2}\). We demonstrate that this inequality is sharp, with equality holding exclusively for the complete bipartite graph \(K_{n_1,n_2}\).
References
[1] H. Haruo; N. Umpei; H. Sachiko, “Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices”, J. Chem. Infor. and Model., vol. 34, no. 2, pp. 428–431, Feb. 1994. doi: 10.1021/ci00018a033.
[2] F. Chung, L. Linyuan, Complex graphs and networks, CBMS Reg. Conf. Ser. Math., no. 107, American Math. Soc., 2006. doi: 10.1090/cbms/107.
[3] D. Kempe, J. M. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network”, Proc. 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 137–146, Aug. 2003. doi: 10.1145/956750.956769.
[4] P. Van Mieghem, J. Omic, R.E. Kooij, “Virus spread in networks”, IEEE/ACM Trans. Netw., vol. 17, no. 1, pp. 1–14, Feb. 2009. doi: 10.1109/TNET.2008.925623.
[5] C. Nowzari, V. M. Preciado, and G. J. Pappas, “Analysis and control of epidemics: A survey of spreading processes on complex networks”, IEEE Control Syst., vol. 36, pp. 26–46, Jan. 2016. doi: 10.1109/MCS.2015.2495000.
[6] W. Chen, C. Castillo, L. V. Lakshmanan, Information and influence propagation in social networks, Synthesis lec. on data management, Morgan & Claypool Pub., no. 37, 2014. doi: 10.2200/S00527ED1V01Y201308DTM037.
[7] H. S. Wilf, “The Eigenvalues of a Graph and its Chromatic Number”, J. London Math. Soc., vol. 42, pp. 330–332, Feb. 1967. doi: 10.1112/jlms/s1-42.1.330.
[8] R. A. Brualdi, A. J. Hoffman, “On the spectral radius of (0, 1) matrices”, Linear Alg. Appl., vol. 65, pp. 133–146, Feb. 1985. doi: 10.1016/0024-3795(85)90092-8.
[9] R. P. Stanley, “A bound on the spectral radius of graphs with e edges”, Linear Alg. Appl., vol. 87, pp. 267–269, Mar. 1987. doi: 10.1016/0024-3795(88)90183-8.
[10] Y. Hong, “A bound on the spectral radius of graphs”, Linear Alg. Appl., vol. 108, pp. 135–139, Sep. 1988. doi: 10.1006/jctb.2000.1997.
[11] V. Nikiforov, “Some inequalities for the largest eigenvalue of a graph”, Combin. Probab. Comp., vol. 11, pp. 179–189, Apr. 2002. doi: 10.1017/S0963548301004928.
[12] D. Cvetković, P. Rowlinson, S.K. Simić, An Introduction to the Theory of Graph Spectra, London Math. Soc., Student Texts, vol. 75, Cambridge Univ. Press, Cambridge, 2010. doi: 10.1017/CBO9780511801518.
[13] P. Van Mieghem, Graph spectra for complex networks, Cambridge University Press, Cambridge, 2011. doi: 10.1017/CBO9780511921681.
[14] A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, 2012. doi: 10.1007/978-1-4614-1939-6.
[15] E. Nosal, Eigenvalues of graphs, Master’s thesis, Univ. of Calgary, 1970.
[16] S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite Graphs and their Applications, Cambridge Univ. Press, 1998. doi: 10.1017/CBO9780511984068.
[17] C. Li, H. Wang, P. Van Mieghem, “Bounds for the spectral radius of graph when nodes are removed”, Linear Alg. Appl., vol. 437, no. 1, pp. 319–323, July 2012. doi: 10.1016/j.laa.2012.02.023.
[18] J.-M. Guo, Z.-W. Wang, X. Li, “Sharp upper bounds of the spectral radius of a graph”, Discrete Math., vol. 342, no. 9, pp. 2559–2563, Sep. 2019. doi: 10.1016/j.disc.2019.05.017.
[19] S. Sun, K. C. Das, “A conjecture on the spectral radius of graphs”, Linear Alg. Appl., vol. 588, pp. 74–80, Mar. 2020 doi: 10.1016/j.laa.2019.11.028.
[20] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, A. Vespignani, “Epidemic processes in complex networks”, Rev. Mod. Phys., vol. 87, pp. 925–979., Aug. 2015. doi: 10.1103/RevModPhys.87.925.
[21] T. C. Silva; L. Zhao, Machine learning in complex networks, Springer, Cham, 2016. doi: 10.1007/978-3-319-17290-3.
Downloads
Published
How to Cite
Volume and Issue
Section
Copyright and License
Copyright (c) 2025 Phi-Dung Hoang
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
