×

zbMATH — the first resource for mathematics

Reflexive bipartite regular graphs. (English) Zbl 1282.05125
Summary: A graph is called reflexive if its second largest eigenvalue does not exceed 2. In this paper, we determine all reflexive bipartite regular graphs. Any bipartite regular graph of degree at most 2 is reflexive as well as its bipartite complement. Apart from them, there is a finite number of resulting graphs.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05B05 Combinatorial aspects of block designs
Software:
nauty
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bussemaker, F. C.; Cvetković, D., There are exactly 13 connected, cubic, integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., 544-576, 43-48, (1976) · Zbl 0357.05064
[2] Colbourn, C. J.; Dinitz, J. H., Handbook of combinatorial designs, (2006), Chapman and Hall/CRC
[3] Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs - theory and application, (1995), Johann Ambrosius Barth Verlag Heidelberg, Leipzig · Zbl 0824.05046
[4] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616, (1995) · Zbl 0831.05044
[5] Neumaier, A.; Seidel, J. J., Discrete hyperbolic geometry, Combinatorica, 3, 2, 219-237, (1983) · Zbl 0523.51016
[6] Koledin, T.; Stanić, Z., Some spectral inequalities for triangle-free regular graphs, Filomat, (2013), submitted for publication · Zbl 1391.05170
[7] Koledin, T.; Stanić, Z., Regular graphs with small second largest eigenvalue, Appl. Anal. Discrete Math., (2013), in press · Zbl 1313.05229
[8] McKay, B. D., Nauty userʼs guide (version 2.2), (2006), Technical report
[9] Rašajski, M.; Radosavljević, Z.; Mihajlović, B., Maximal reflexive cacti with four cycles: the approach via Smith graphs, Linear Algebra Appl., 435, 2530-2543, (2011) · Zbl 1222.05176
[10] Schwenk, A. J., Exactly thirteen connected cubic graphs have integral spectra, (Alavi, Y.; Lick, D., Theory and Applications of Graphs, Lecture Notes in Math., vol. 642, (1978), Springer-Verlag Berlin, Heidelberg), 516-533 · Zbl 0376.05050
[11] Stevanović, D., 4-regular integral graphs avoiding ±3 in the spectrum, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 14, 99-110, (2003) · Zbl 1088.05504
[12] Teranishi, Y.; Yasuno, F., The second largest eigenvalues of regular bipartite graphs, Kyushu J. Math., 54, 39-54, (2000) · Zbl 0990.05095
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.