A Descent on Simple Graphs -- from Complete to Cycle -- and Algebraic Properties of Their Spectra

2017/11/15 by Mönius, Katja, Steuding, Jörn, Stumpf, Pascal
#05C50 #11R04 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1711.05500

Abstract

We investigate a descent on simple graphs, starting with the complete graph on n vertices and ending up with the cycle graph by removing one edge after another. We obtain quantitative results showing that graphs with large diameter must have some eigenvalues of large algebraic degree.

Related

• Proof of a conjecture on `plateaux' phenomenon of graph Laplacian eigenvalues
• Graphs with two main and two plain eigenvalues
• Spectral characterization of the complete graph removing a path of small length
• Bounding the number of cycles in a graph in terms of its degree sequence
• Bounds on graph eigenvalues I