zbMATH — the first resource for mathematics

Degree maximal graphs are Laplacian integral. (English) Zbl 0795.05091
A graph is maximal if its degree sequence is majorized by no other graphic sequence. The author presents an algorithmic construction of all maximal graphs. It follows that the Laplacian spectrum of a maximal graph is the conjugate of its degree sequence.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[1] Chvatal, V., On Hamilton’s ideals, J. combin. theory ser. B, 12, 163-168, (1972) · Zbl 0213.50803
[2] R. Grone and R. Merris, The Laplacian spectrum of a graph, II, SIAM J. Discrete Math., to appear. · Zbl 0795.05092
[3] Marshall, A.W.; Olkin, I., Inequalities: theory of majorization and its applications, (1979), Academic New York · Zbl 0437.26007
[4] Ruch, E.; Gutman, I., The branching extent of graphs, J. combin. inform. system sci., 4, 285-295, (1979) · Zbl 0461.05057
[5] Sierksma, G.; Hoogeveen, H., Seven criteria for integer sequences being graphic, J. graph theory, 15, 223-231, (1991) · Zbl 0752.05052
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.