On the number of edges in a graph with no (k+1)-connected subgraphs

Anton Bernshteyn; Alexandr Kostochka

doi:10.1016/j.disc.2015.10.014

On the number of edges in a graph with no (k+1)-connected subgraphs

Anton Bernshteyn, Alexandr Kostochka

Mathematics

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

Abstract

Mader proved that for k≥1 and n≥2k, every n-vertex graph with no (k+1)-connected subgraphs has at most (Formula presented.) edges. He also conjectured that for n large with respect to k, every such graph has at most (Formula presented.) edges. Yuster improved Mader's upper bound to (Formula presented.). In this note, we make the next step towards Mader's Conjecture: we improve Yuster's bound to (Formula presented.) for (Formula presented.).

Original language	English (US)
Pages (from-to)	682-688
Number of pages	7
Journal	Discrete Mathematics
Volume	339
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2015.10.014
State	Published - Feb 6 2016

Keywords

Average degree
Connectivity
k-connected subgraphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2015.10.014

Library availability

Discover UIUC Full Text

Cite this

@article{bc2bb1a5d0b1499eb45f92e91b277c21,

title = "On the number of edges in a graph with no (k+1)-connected subgraphs",

abstract = "Mader proved that for k≥1 and n≥2k, every n-vertex graph with no (k+1)-connected subgraphs has at most (Formula presented.) edges. He also conjectured that for n large with respect to k, every such graph has at most (Formula presented.) edges. Yuster improved Mader's upper bound to (Formula presented.). In this note, we make the next step towards Mader's Conjecture: we improve Yuster's bound to (Formula presented.) for (Formula presented.).",

keywords = "Average degree, Connectivity, k-connected subgraphs",

author = "Anton Bernshteyn and Alexandr Kostochka",

note = "Publisher Copyright: {\textcopyright} 2015 Published by Elsevier B.V.",

year = "2016",

month = feb,

day = "6",

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

language = "English (US)",

volume = "339",

pages = "682--688",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - On the number of edges in a graph with no (k+1)-connected subgraphs

AU - Bernshteyn, Anton

AU - Kostochka, Alexandr

PY - 2016/2/6

Y1 - 2016/2/6

N2 - Mader proved that for k≥1 and n≥2k, every n-vertex graph with no (k+1)-connected subgraphs has at most (Formula presented.) edges. He also conjectured that for n large with respect to k, every such graph has at most (Formula presented.) edges. Yuster improved Mader's upper bound to (Formula presented.). In this note, we make the next step towards Mader's Conjecture: we improve Yuster's bound to (Formula presented.) for (Formula presented.).

AB - Mader proved that for k≥1 and n≥2k, every n-vertex graph with no (k+1)-connected subgraphs has at most (Formula presented.) edges. He also conjectured that for n large with respect to k, every such graph has at most (Formula presented.) edges. Yuster improved Mader's upper bound to (Formula presented.). In this note, we make the next step towards Mader's Conjecture: we improve Yuster's bound to (Formula presented.) for (Formula presented.).

KW - Average degree

KW - Connectivity

KW - k-connected subgraphs

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

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

U2 - 10.1016/j.disc.2015.10.014

DO - 10.1016/j.disc.2015.10.014

M3 - Article

AN - SCOPUS:84945976058

SN - 0012-365X

VL - 339

SP - 682

EP - 688

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

On the number of edges in a graph with no (k+1)-connected subgraphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this