Mohar, Bojan; Tayfeh-Rezaie, Behruz Median eigenvalues of bipartite graphs. (English) Zbl 1317.05112 J. Algebr. Comb. 41, No. 3, 899-909 (2015). The HL-index of an \(n\)-vertex graph \(G\) with eigenvalues \(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_n\) is \[ R(G) = \max\left\{\left|\lambda_{\left\lfloor\frac{n+1}2\right\rfloor}\right|, \left|\lambda_{\left\lceil \frac{n+1}2\right\rceil}\right|\right\} \] (cf.[G. Jaklič et al., Ars Math. Contemp. 5, No. 1, 99–105 (2012; Zbl 1244.05144)]). The main result of this paper is: Let \(G\) be a connected bipartite graph with maximum degree \(\Delta\geq3.\) Then \(R(G)\leq\sqrt{\Delta-2}\) unless \(G\) is the incidence graph of a projective plane of order \(\Delta-1\), in which case \(R(G)=\sqrt{\Delta-1}\). From the authors’ abstract: “We also present an approach through graph covering to construct infinite graphs with large \(HL\)-index.” They report that one of their theorems was obtained previously in [J. H. Kwak and J. Lee, Linear Multilinear Algebra 32, No. 1, 61–73 (1992; Zbl 0755.05078)] and generalized in [R. Feng et al., Bull. Aust. Math. Soc. 69, No. 1, 133–136 (2004; Zbl 1043.05075)]. Reviewer: William G. Brown (Montréal) Cited in 6 Documents MSC: 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:adjacency matrix; graph eigenvalues; median eigenvalues; covers Citations:Zbl 1244.05144; Zbl 0755.05078; Zbl 1043.05075 PDFBibTeX XMLCite \textit{B. Mohar} and \textit{B. Tayfeh-Rezaie}, J. Algebr. Comb. 41, No. 3, 899--909 (2015; Zbl 1317.05112) Full Text: DOI arXiv References: [1] Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gap. Combinatorica 26, 495-519 (2006) · Zbl 1121.05054 · doi:10.1007/s00493-006-0029-7 [2] Cvetković, D., Rowlinson, P., Simić, S.: Spectral generalizations of line graphs, On graphs with least eigenvalue 2. London Mathematical Society Lecture Notes Series 314. Cambridge University Press, Cambridge (2004) · Zbl 1061.05057 [3] Feng, R., Kwak, J.H., Lee, J.: Characteristic polynomials of graph coverings. B. Aust. Math. Soc. 69, 133-136 (2004) · Zbl 1043.05075 [4] Fowler, P.W., Pisanski, T.: HOMO-LUMO maps for fullerenes. Acta Chim. Slov. 57, 513-517 (2010) [5] Fowler, P.W., Pisanski, T.: HOMO-LUMO maps for chemical graphs. MATCH Commun. Math. Comput. Chem. 64, 373-390 (2010) · Zbl 1265.05574 [6] Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, Berlin (2001) · Zbl 0968.05002 · doi:10.1007/978-1-4613-0163-9 [7] Gross, J.L.: Voltage Graphs. In: Jonathan, L. (ed.) Handbook of Graph Theory, Discrete Mathematics and its Applications, pp. 783-805. CRC Press, Boca Raton (2004) [8] Guo, K., Mohar, B.: Large regular bipartite graphs with median eigenvalue 1, submitted. arXiv:1309.7025 · Zbl 1286.05087 [9] Gutman, I., Polanski, O.E.: Mathematical Concepts in Organic Chemistry. Springer-Verlag, Berlin (1986) · Zbl 0657.92024 · doi:10.1007/978-3-642-70982-1 [10] Hall, M.: Combinatorial Theory, 2nd edn. Wiley, Hoboken (1986) · Zbl 0588.05001 [11] Jaklič, G., Fowler, P.W., Pisanski, T.: HL-index of a graph. Ars Math. Contemp. 5, 99-105 (2012) · Zbl 1244.05144 [12] Kovacs, I., Silver, D.S., Williams, S.G.: Determinants of commuting-block matrices. Amer. Math. Monthly 106, 950-952 (1999) · Zbl 0981.15005 · doi:10.2307/2589750 [13] Kwak, J.H., Lee, J.: Characteristic polynomials of some graph bundles II. Linear Multilinear A. 32, 61-73 (1992) · Zbl 0755.05078 [14] Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families I: Bipartite Ramanujan graphs of all degrees, arXiv:1304.4132 · Zbl 1316.05066 [15] Marcus, A., Spielman, D.A., Srivastava, N.: Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer Problem, arXiv:1306.3969 · Zbl 1332.46056 [16] Mohar, B.L.: Median eigenvalues of bipartite subcubic graphs, Combin. Probab. Comput., in press. arXiv: 1309.7395 · Zbl 1372.05129 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.