×

Median eigenvalues of bipartite graphs. (English) Zbl 1317.05112

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)].

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.)
PDFBibTeX XMLCite
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.