Back to Search Start Over

Bounding the number of cycles in a graph in terms of its degree sequence

Authors :
Natasha Morrison
Jonathan A. Noel
Luke Postle
Sergey Norin
Zdeněk Dvořák
Source :
European Journal of Combinatorics. 91:103206
Publication Year :
2021
Publisher :
Elsevier BV, 2021.

Abstract

We give an upper bound on the number of cycles in a simple graph in terms of its degree sequence, and apply this bound to resolve several conjectures of Kiraly (2009) and Arman and Tsaturian (2017) and to improve upper bounds on the maximum number of cycles in a planar graph.

Details

ISSN :
01956698
Volume :
91
Database :
OpenAIRE
Journal :
European Journal of Combinatorics
Accession number :
edsair.doi...........3ef32a2169fe3223d685c5db2c6ebd5c
Full Text :
https://doi.org/10.1016/j.ejc.2020.103206