Regular graphs with maximal energy per vertex. (English) Zbl 1298.05217
Summary: We study the energy per vertex in regular graphs. For every \(k \geq 2\), we give an upper bound for the energy per vertex of a \(k\)-regular graph, and show that a graph attains the upper bound if and only if it is the disjoint union of incidence graphs of projective planes of order \(k - 1\) or, in case \(k = 2\), the disjoint union of triangles and hexagons. For every \(k\), we also construct \(k\)-regular subgraphs of incidence graphs of projective planes for which the energy per vertex is close to the upper bound. In this way, we show that this upper bound is asymptotically tight.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 51E20 | Combinatorial structures in finite projective spaces |
References:
| [1] | Aigner, M.; Ziegler, G. M., Proofs from THE BOOK (2004), Springer · Zbl 1098.00001 |
| [2] | Baker, R. D., An elliptic semiplane, J. Combin. Theory Ser. A, 25, 193-195 (1978) · Zbl 0433.05017 |
| [3] | Baker, R. C.; Harman, G.; Pintz, J., The difference between consecutive primes, II, Proc. Lond. Math. Soc. (3), 83, 532-562 (2001) · Zbl 1016.11037 |
| [4] | Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (2012), Springer, available online at · Zbl 1231.05001 |
| [5] | Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin, New York · Zbl 0747.05073 |
| [7] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1979), VEB Deutscher Verlag der Wissenschaften: VEB Deutscher Verlag der Wissenschaften Berlin |
| [8] | De Winter, S.; Lazebnik, F.; Verstraëte, J., An extremal characterization of projective planes, Electron. J. Combin., 15, R143 (2008) · Zbl 1178.05024 |
| [9] | Fiorini, G.; Lazebnik, F., An extremal characterization of incidence graphs of projective planes, Acta Appl. Math., 52, 257-260 (1998) · Zbl 0911.05037 |
| [10] | Gutman, I., The energy of a graph, Ber. Math. Stat. Sekt. Forschungszent. Graz., 103, 1-22 (1978) · Zbl 0402.05040 |
| [11] | Koolen, J. H.; Moulton, V., Maximal energy graphs, Adv. in Appl. Math., 26, 47-52 (2001) · Zbl 0976.05040 |
| [12] | Li, X.; Shi, Y.; Gutman, I., Graph Energy (2012), Springer · Zbl 1262.05100 |
| [13] | McClelland, B., Properties of the latent roots of a matrix: The estimation of \(π\)-electron energies, J. Chem. Phys., 54, 640-643 (1971) |
| [14] | Nikiforov, V., Graphs and matrices with maximal energy, J. Math. Anal. Appl., 327, 735-738 (2007) · Zbl 1112.05067 |
| [15] | Peressini, A. L.; Sullivan, F. E.; Uhl, J. J., The Mathematics of Nonlinear Programming (1988), Springer · Zbl 0663.90054 |
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.
