Abstract
It is well known that the spectral radius of a tree whose maximum degree is Delta cannot exceed 2 root Delta - 1. A similar upper bound holds for arbitrary planar graphs, whose spectral radius cannot exceed root 8 Delta + 10, and more generally, for all d-degenerate graphs, where the corresponding upper bound is root 4d Delta.
Following this, we say that a graph G is spectrally d-degenerate if every subgraph H of G has spectral radius at most root d Delta(H). In this paper we derive a rough converse of the above-mentioned results by proving that each spectrally d-degenerate graph G contains a vertex whose degree is at most 4d log(2)(Delta(G)/d) (if Delta(G) }= 2d).
It is shown that the dependence on Delta in this upper bound cannot be eliminated, as long as the dependence on d is subexponential. It is also proved that the problem of deciding if a graph is spectrally d-degenerate is Co-NP-complete. (C) 2012 Elsevier Inc.
All rights reserved.