×

On the spectral radius of bi-block graphs with given independence number \(\alpha\). (English) Zbl 1510.05177

Summary: A connected graph is called a bi-block graph if each of its blocks is a complete bipartite graph. Let \(\mathcal{B}(\mathbf{k},\alpha)\) be the class of bi-block graph on \(\mathbf{k}\) vertices with given independence number \(\alpha\). It is easy to see that every bi-block graph is a bipartite graph. For a bipartite graph \(G\) on \(\mathbf{k}\) vertices, the independence number \(\alpha(G)\) satisfies \(\lceil\frac{\mathbf{k}}{2}\rceil\leq\alpha(G)\leq\mathbf{k}-1\). In this article, we prove that the maximum spectral radius \(\rho(G)\) among all graphs \(G\) in \(\mathcal{B}(\mathbf{k},\alpha)\), is uniquely attained for the complete bipartite graph \(K_{\alpha,\mathbf{k}-\alpha}\).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bapat, R. B., Graphs and Matrices (2014), Hindustan Book Agency: Hindustan Book Agency New Delhi · Zbl 1288.05152
[2] Conde, C. M.; Dratman, E.; Grippo, L. N., On the spectral radius of block graphs with prescribed independence number \(\alpha \), Linear Algebra Appl. (2020)
[3] Feng, L.; Song, J., Spectral radius of unicyclic graphs with given independence number, Util. Math., 84, 33-43 (2011) · Zbl 1228.05205
[4] Guo, J. M.; Shao, J. Y., On the spectral radius of trees with fixed diameter, Linear Algebra Appl., 413, 131-147 (2006) · Zbl 1082.05060
[5] Ji, C.; Lu, M., On the spectral radius of trees with given independence number, Linear Algebra Appl., 488, 102-108 (2016) · Zbl 1326.05084
[6] Li, Q.; Feng, K. Q., On the largest eigenvalue of a graph, (Chinese), Acta Math. Appl. Sin., 2, 167-175 (1979)
[7] Liu, H.; Lu, M.; Tian, F., On the spectral radius of graphs with cut edges, Linear Algebra Appl., 389, 139-145 (2004) · Zbl 1053.05080
[8] Lu, H.; Lin, Y., Maximum spectral radius of graphs with given connectivity, minimum degree and independence number, J. Discret. Algorithms, 31, 113-119 (2015) · Zbl 1325.05107
[9] Wu, B.; Xiao, E.; Hong, Y., The spectral radius of trees on k pendant vertices, Linear Algebra Appl., 395, 343-349 (2005) · Zbl 1057.05057
[10] Xu, M.; Hong, Y.; Shu, J.; Zhai, M., The minimum spectral radius of graphs with a given independence number, Linear Algebra Appl., 431, 5, 937-945 (2009) · Zbl 1168.05335
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.