Cycles containing all the odd-degree vertices

Kathie Cameron; Carsten Thomassen

doi:10.1016/j.jctb.2019.12.003

Cycles containing all the odd-degree vertices

Kathie Cameron, Carsten Thomassen

Department of Applied Mathematics and Computer Science

Wilfrid Laurier University

Research output: Contribution to journal › Journal article › Research › peer-review

171 Downloads (Pure)

Abstract

The number of cycles in a graph containing any fixed edge and also containing all vertices of odd degree is odd if and only if all vertices have even degree. If all vertices have even degree this is a theorem of Shunichi Toida. If all vertices have odd degree it is Andrew Thomason's extension of Smith's theorem.

Original language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	143
Pages (from-to)	219-225
ISSN	0095-8956
DOIs	https://doi.org/10.1016/j.jctb.2019.12.003
Publication status	Published - 1 Jan 2020

Keywords

Eulerian graph
Hamiltonian cycle
Lifting a vertex
Parity theorem

Access to Document

10.1016/j.jctb.2019.12.003

FulltextAccepted author manuscript, 437 KBLicence: CC BY-NC-ND

OpenUrl availability

Full text

Cite this

@article{073567a946c74bf1a2ef9f11353fb777,

title = "Cycles containing all the odd-degree vertices",

abstract = "The number of cycles in a graph containing any fixed edge and also containing all vertices of odd degree is odd if and only if all vertices have even degree. If all vertices have even degree this is a theorem of Shunichi Toida. If all vertices have odd degree it is Andrew Thomason's extension of Smith's theorem.",

keywords = "Eulerian graph, Hamiltonian cycle, Lifting a vertex, Parity theorem",

author = "Kathie Cameron and Carsten Thomassen",

year = "2020",

month = jan,

day = "1",

doi = "10.1016/j.jctb.2019.12.003",

language = "English",

volume = "143",

pages = "219--225",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press",

}

TY - JOUR

T1 - Cycles containing all the odd-degree vertices

AU - Cameron, Kathie

AU - Thomassen, Carsten

PY - 2020/1/1

Y1 - 2020/1/1

N2 - The number of cycles in a graph containing any fixed edge and also containing all vertices of odd degree is odd if and only if all vertices have even degree. If all vertices have even degree this is a theorem of Shunichi Toida. If all vertices have odd degree it is Andrew Thomason's extension of Smith's theorem.

AB - The number of cycles in a graph containing any fixed edge and also containing all vertices of odd degree is odd if and only if all vertices have even degree. If all vertices have even degree this is a theorem of Shunichi Toida. If all vertices have odd degree it is Andrew Thomason's extension of Smith's theorem.

KW - Eulerian graph

KW - Hamiltonian cycle

KW - Lifting a vertex

KW - Parity theorem

U2 - 10.1016/j.jctb.2019.12.003

DO - 10.1016/j.jctb.2019.12.003

M3 - Journal article

AN - SCOPUS:85077390946

SN - 0095-8956

VL - 143

SP - 219

EP - 225

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Cycles containing all the odd-degree vertices

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this