Strongly regular graphs with maximal energy. (English) Zbl 1152.05060
Summary: The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. Koolen and Moulton have proved that the energy of a graph on \(n\) vertices is at most \(n(1+\sqrt n)/2\), and that equality holds if and only if the graph is strongly regular with parameters \((n,(n+\sqrt n)/2, (n+2\sqrt n)/4, (n+2\sqrt n)/4\). Such graphs are equivalent to a certain type of Hadamard matrices. Here we survey constructions of these Hadamard matrices and the related strongly regular graphs.
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
References:
| [1] | Brouwer, A. E., Strongly regular graphs, (Colbourn, C. J.; Denitz, J. H., Handbook of Combinatorial Designs (2007), Chapman & Hall/CRC press: Chapman & Hall/CRC press Boca Raton), (Chapter VII.11) · Zbl 0538.05024 |
| [2] | Craigen, R.; Kharaghani, H., Hadamard matrices and Hadamard designs, (Colbourn, C. J.; Denitz, J. H., Handbook of Combinatorial Designs (2007), Chapman & Hall/CRC press: Chapman & Hall/CRC press Boca Raton), (Chapter V.1) · Zbl 0810.05018 |
| [3] | Gutman, I., The energy of a graph: old and new results, (Betten, A.; Kohner, A.; Laue, R.; Wassermann, A., Algebraic Combinatorics and Applications (2001), Springer: Springer Berlin), 196-211 · Zbl 0974.05054 |
| [4] | Haemers, W. H., Matrices and graphs, (Hogben, Leslie, Handbook of Linear Algebra (2007), Chapman & Hall/CRC press: Chapman & Hall/CRC press Boca Raton), (Chapter 28) · Zbl 0745.51003 |
| [5] | Jørgensen, L. K.; Klin, M., Switching of edges in strongly regular graphs I: a family of partial difference sets on 100 vertices, Electron. J. Combin., 10, R17 (2003) · Zbl 1011.05063 |
| [6] | Kharaghani, H., New classes of weighing matrices, Ars Combin., 19, 69-72 (1985) · Zbl 0584.05015 |
| [7] | Koolen, J. H.; Moulton, V., Maximal energy graphs, Adv. Appl. Math., 26, 47-52 (2001) · Zbl 0976.05040 |
| [8] | McKay, B. D.; Spence, E., The classification of regular two-graphs on 36 and 38 vertices, Australas. J. Combin., 24, 293-300 (2001) · Zbl 0979.05110 |
| [9] | Muzychuk, M.; Xiang, Q., Symmetric Bush-type Hadamard matrices of order \(4m^4\) exist for all odd m, Proc. Amer. Math. Soc., 134, 2197-2204 (2006) · Zbl 1088.05020 |
| [10] | Paley, R. E.A. C., On orthogonal matrices, J. Math. Phys. MIT, 12, 311-320 (1933) · Zbl 0007.10004 |
| [11] | Seidel, J. J., Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3, Linear Algebra Appl., 1, 281-298 (1968) · Zbl 0159.25403 |
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.
