The minimum spectral radius of Kr+1-saturated graphs

Jaehoon Kim; Seog Jin Kim; Alexandr V. Kostochka; Suil O

doi:10.1016/j.disc.2020.112068

The minimum spectral radius of K_r+1-saturated graphs

Jaehoon Kim, Seog Jin Kim, Alexandr V. Kostochka, Suil O

Mathematics

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

Abstract

For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e∈E(G¯), G+e contains H. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in n-vertex K_r+1-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed r and n→∞.

Original language	English (US)
Article number	112068
Journal	Discrete Mathematics
Volume	343
Issue number	11
DOIs	https://doi.org/10.1016/j.disc.2020.112068
State	Published - Nov 2020

Keywords

Complete graphs
Saturated graphs
Spectral radius

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2020.112068

Library availability

Discover UIUC Full Text

Cite this

@article{f51c550590e34e6989fe59f40cd78686,

title = "The minimum spectral radius of Kr+1-saturated graphs",

abstract = "For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e∈E(G¯), G+e contains H. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in n-vertex Kr+1-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed r and n→∞.",

keywords = "Complete graphs, Saturated graphs, Spectral radius",

author = "Jaehoon Kim and Kim, {Seog Jin} and Kostochka, {Alexandr V.} and Suil O",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = nov,

doi = "10.1016/j.disc.2020.112068",

language = "English (US)",

volume = "343",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - The minimum spectral radius of Kr+1-saturated graphs

AU - Kim, Jaehoon

AU - Kim, Seog Jin

AU - Kostochka, Alexandr V.

AU - O, Suil

PY - 2020/11

Y1 - 2020/11

N2 - For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e∈E(G¯), G+e contains H. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in n-vertex Kr+1-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed r and n→∞.

AB - For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e∈E(G¯), G+e contains H. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in n-vertex Kr+1-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed r and n→∞.

KW - Complete graphs

KW - Saturated graphs

KW - Spectral radius

UR - http://www.scopus.com/inward/record.url?scp=85087696853&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087696853&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2020.112068

DO - 10.1016/j.disc.2020.112068

M3 - Article

AN - SCOPUS:85087696853

SN - 0012-365X

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

M1 - 112068

ER -