A Note on Degenerate and Spectrally Degenerate Graphs. Issue 1 (1st May 2012)

• Record Type: Journal Article
• Authors: Alon, Noga
• Is Part Of: Journal of graph theory. Volume 72:Issue 1(2013)
• Page Start: 1
• Page End: 6
• Publication Date: 2012-05-01
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21627
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A graph <italic>G</italic> is called spectrally <italic>d</italic>‐degenerate if the largest eigenvalue of each subgraph of it with maximum degree <italic>D</italic> is at most <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2kd9r70" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:jgt21627:equation:jgt21627-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msqrt><mml:mrow><mml:mi>d</mml:mi><mml:mi>D</mml:mi></mml:mrow></mml:msqrt></mml:math></alternatives></inline-formula>. We prove that for every constant <italic>M</italic> there is a graph with minimum degree <italic>M</italic>, which is spectrally 50‐degenerate. This settles a problem of Dvořák and Mohar (Spectrally degenerate graphs: Hereditary case, arXiv: 1010.3367).</p> </abstract>