R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199 (1994), 381-389. Research supported by the National Security Agency under grant no. MDA904-90-H-4024. Math Reviews 95e:05083.

A degree maximal (or threshold) graph with m edges is one whose degree sequence is maximal, with respect to majorization, among the graphic partitions of 2m. The main result of this article is that G is a threshold graph if and only if its Laplacian spectrum is equal to the conjugate of its degree sequence. Among the publications citing this article are:

  • D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs, 3rd. ed., Johann Ambrosius Barth Verlag, Heidelberg, 1995.
  • W. So, Rank one perturbation and its application to the Laplacian spectrum of a graph, Linear & Multilinear Algebra 46 (1999), 193-198.
  • A. Berman and X.-D. Zhang, Linear & Multilinear Algebra 47 (2000), 307-311.
  • S. J. Kirkland, J. J. Molitierno, and M. Neumann, Linear & Multilinear Algebra 48 (2001), 237-246.
  • S. J. Kirkland, J. J. Molitierno, M. Neumann, and B. L. Shader, Linear Algebra Appl. 341 (2002), 45-56.
  • F. Yizheng, Linear & Multilinear Algebra 50 (2002), 133-142.
  • D. D. Olesky, A. Roy, and P. van den Driessche, Linear Algebra Appl. 346 (2002), 109-130.
  • H. Christianson and V. Reiner, Linear Algebra Appl. 349 (2002), 233-244.
  • A. M. Duval and V. Reiner, Trans. Amer. Math. Soc. 354 (2002), 4313-4344.
  • Y. Z. Fan, Linear & Multilinear Algebra 50 (2002), 133-142.
  • S. Friedland and R. Nabben, J. Graph Theory 41 (2002), 1-17.
  • R. B. Ellis, III, PhD Dissertation, UC San Diego, 2002. [ .ps; .pdf]
  • Y. Z. Fan, Linear & Multilinear Algebra 51 (2003), 147-154.
  • Y. Z. Fan, Linear Algebra Appl. 374 (2003), 307-316.
  • J. L. Martin and V. Reiner, J. Combinatorial Theory A104 (2003), 287-300.
  • S. Kirkland, Discrete Math. 295 (2005), 75-90.