On a property of 2-connected graphs and Dirac's Theorem

Alexandr Kostochka; Ruth Luo; Grace McCourt

doi:10.1016/j.disc.2024.114153

On a property of 2-connected graphs and Dirac's Theorem

Alexandr Kostochka, Ruth Luo, Grace McCourt

Mathematics

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

Abstract

We refine a property of 2-connected graphs described in the classical paper of Dirac from 1952 and use the refined property to somewhat shorten Dirac's proof of the fact that each 2-connected n-vertex graph with minimum degree at least k has a cycle of length at least min⁡{n,2k}.

Original language	English (US)
Article number	114153
Journal	Discrete Mathematics
Volume	347
Issue number	11
DOIs	https://doi.org/10.1016/j.disc.2024.114153
State	Published - Nov 2024

Keywords

Berge cycles
Extremal hypergraph theory
Minimum degree

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2024.114153

Library availability

Discover UIUC Full Text

Cite this

@article{e0c23faaa6e945719031e9bf05ba38fb,

title = "On a property of 2-connected graphs and Dirac's Theorem",

abstract = "We refine a property of 2-connected graphs described in the classical paper of Dirac from 1952 and use the refined property to somewhat shorten Dirac's proof of the fact that each 2-connected n-vertex graph with minimum degree at least k has a cycle of length at least min⁡{n,2k}.",

keywords = "Berge cycles, Extremal hypergraph theory, Minimum degree",

author = "Alexandr Kostochka and Ruth Luo and Grace McCourt",

note = "Publisher Copyright: {\textcopyright} 2024 The Authors",

year = "2024",

month = nov,

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

language = "English (US)",

volume = "347",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "11",

}

TY - JOUR

T1 - On a property of 2-connected graphs and Dirac's Theorem

AU - Kostochka, Alexandr

AU - Luo, Ruth

AU - McCourt, Grace

PY - 2024/11

Y1 - 2024/11

N2 - We refine a property of 2-connected graphs described in the classical paper of Dirac from 1952 and use the refined property to somewhat shorten Dirac's proof of the fact that each 2-connected n-vertex graph with minimum degree at least k has a cycle of length at least min⁡{n,2k}.

AB - We refine a property of 2-connected graphs described in the classical paper of Dirac from 1952 and use the refined property to somewhat shorten Dirac's proof of the fact that each 2-connected n-vertex graph with minimum degree at least k has a cycle of length at least min⁡{n,2k}.

KW - Berge cycles

KW - Extremal hypergraph theory

KW - Minimum degree

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

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

U2 - 10.1016/j.disc.2024.114153

DO - 10.1016/j.disc.2024.114153

M3 - Article

AN - SCOPUS:85198387591

SN - 0012-365X

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

M1 - 114153

ER -

On a property of 2-connected graphs and Dirac's Theorem

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this