A Note on Degenerate and Spectrally Degenerate Graphs. Issue 1 (1st May 2012) - Alon, Noga
Abstract A graph G is called spectrally d‐degenerate if the largest eigenvalue of each subgraph of it with maximum degree D is at most <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2kd9r70" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />dD</alternatives>. We prove that for every constant M there is a graph with minimum degree M, which is spectrally 50‐degenerate. This settles a problem of Dvořák and Mohar (Spectrally degenerate graphs: Hereditary case, arXiv: 1010.3367).