A note on degenerate and spectrally degenerate graphs

Noga Alon

doi:10.1002/jgt.21627

A note on degenerate and spectrally degenerate graphs

Noga Alon

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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 √dD. 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 Dvorák and Mohar (Spectrally degenerate graphs: Hereditary case, arXiv: 1010.3367).

Original language	English (US)
Pages (from-to)	1-6
Number of pages	6
Journal	Journal of Graph Theory
Volume	72
Issue number	1
DOIs	https://doi.org/10.1002/jgt.21627
State	Published - Jan 2013
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

degenerate graphs
graph eigenvalues
spectral radius

Access to Document

10.1002/jgt.21627

Cite this

@article{38f95c40743241bcacdeb47d8c7c0a96,

title = "A note on degenerate and spectrally degenerate graphs",

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 √dD. 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 Dvor{\'a}k and Mohar (Spectrally degenerate graphs: Hereditary case, arXiv: 1010.3367).",

keywords = "degenerate graphs, graph eigenvalues, spectral radius",

author = "Noga Alon",

year = "2013",

month = jan,

doi = "10.1002/jgt.21627",

language = "English (US)",

volume = "72",

pages = "1--6",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - A note on degenerate and spectrally degenerate graphs

AU - Alon, Noga

PY - 2013/1

Y1 - 2013/1

N2 - A graph G is called spectrally d-degenerate if the largest eigenvalue of each subgraph of it with maximum degree D is at most √dD. 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 Dvorák and Mohar (Spectrally degenerate graphs: Hereditary case, arXiv: 1010.3367).

AB - A graph G is called spectrally d-degenerate if the largest eigenvalue of each subgraph of it with maximum degree D is at most √dD. 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 Dvorák and Mohar (Spectrally degenerate graphs: Hereditary case, arXiv: 1010.3367).

KW - degenerate graphs

KW - graph eigenvalues

KW - spectral radius

UR - https://www.scopus.com/pages/publications/84867898145

UR - https://www.scopus.com/pages/publications/84867898145#tab=citedBy

U2 - 10.1002/jgt.21627

DO - 10.1002/jgt.21627

M3 - Article

AN - SCOPUS:84867898145

SN - 0364-9024

VL - 72

SP - 1

EP - 6

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

A note on degenerate and spectrally degenerate graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this