Triangle-free graphs with the maximum number of cycles

Andrii Arman; David S. Gunderson; Sergei Tsaturian

doi:10.1016/j.disc.2015.10.008

Triangle-free graphs with the maximum number of cycles

Andrii Arman, David S. Gunderson, Sergei Tsaturian

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

6 Citations (Scopus)

Abstract

It is shown that for n≥141, among all triangle-free graphs on n vertices, the balanced complete bipartite graph K_{⌈n/2⌉,⌊n/2⌋} is the unique triangle-free graph with the maximum number of cycles. Using modified Bessel functions, tight estimates are given for the number of cycles in K_{⌈n/2⌉,⌊n/2⌋}. Also, an upper bound for the number of Hamiltonian cycles in a triangle-free graph is given.

Original language	English
Pages (from-to)	699-711
Number of pages	13
Journal	Discrete Mathematics
Volume	339
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2015.10.008
Publication status	Published - 6 Feb 2016
Externally published	Yes

Keywords

Cycle-maximal
Hamiltonian cycles
Maximum number of cycles
Triangle-free

Access to Document

10.1016/j.disc.2015.10.008

Cite this

@article{b8fc2c0903d5404f81d6ff2c3ad4e5fe,

title = "Triangle-free graphs with the maximum number of cycles",

abstract = "It is shown that for n≥141, among all triangle-free graphs on n vertices, the balanced complete bipartite graph K⌈n/2⌉,⌊n/2⌋ is the unique triangle-free graph with the maximum number of cycles. Using modified Bessel functions, tight estimates are given for the number of cycles in K⌈n/2⌉,⌊n/2⌋. Also, an upper bound for the number of Hamiltonian cycles in a triangle-free graph is given.",

keywords = "Cycle-maximal, Hamiltonian cycles, Maximum number of cycles, Triangle-free",

author = "Andrii Arman and Gunderson, {David S.} and Sergei Tsaturian",

year = "2016",

month = feb,

day = "6",

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

language = "English",

volume = "339",

pages = "699--711",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Triangle-free graphs with the maximum number of cycles

AU - Arman, Andrii

AU - Gunderson, David S.

AU - Tsaturian, Sergei

PY - 2016/2/6

Y1 - 2016/2/6

N2 - It is shown that for n≥141, among all triangle-free graphs on n vertices, the balanced complete bipartite graph K⌈n/2⌉,⌊n/2⌋ is the unique triangle-free graph with the maximum number of cycles. Using modified Bessel functions, tight estimates are given for the number of cycles in K⌈n/2⌉,⌊n/2⌋. Also, an upper bound for the number of Hamiltonian cycles in a triangle-free graph is given.

AB - It is shown that for n≥141, among all triangle-free graphs on n vertices, the balanced complete bipartite graph K⌈n/2⌉,⌊n/2⌋ is the unique triangle-free graph with the maximum number of cycles. Using modified Bessel functions, tight estimates are given for the number of cycles in K⌈n/2⌉,⌊n/2⌋. Also, an upper bound for the number of Hamiltonian cycles in a triangle-free graph is given.

KW - Cycle-maximal

KW - Hamiltonian cycles

KW - Maximum number of cycles

KW - Triangle-free

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

U2 - 10.1016/j.disc.2015.10.008

DO - 10.1016/j.disc.2015.10.008

M3 - Article

AN - SCOPUS:84945949991

SN - 0012-365X

VL - 339

SP - 699

EP - 711

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

Triangle-free graphs with the maximum number of cycles

Abstract

Keywords

Access to Document

Other files and links

Cite this