On a Question of van Aardt et al. on Destroying All Longest Cycles

We describe an infinite family of 2-connected graphs, each of which has the property that the intersection of all longest cycles is empty. In particular, we present such graphs with circumference 10, 13, and 16. This settles a question of van Aardt et al. (Discrete Appl Math 186:251–259, 2015 ) conc...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2019-03, Vol.35 (2), p.479-483
Main Author: Zamfirescu, Carol T.
Format: Article
Language:English
Subjects:
Circumferences
Combinatorics
Engineering Design
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe an infinite family of 2-connected graphs, each of which has the property that the intersection of all longest cycles is empty. In particular, we present such graphs with circumference 10, 13, and 16. This settles a question of van Aardt et al. (Discrete Appl Math 186:251–259, 2015 ) concerning the existence of such graphs for all but one case, namely circumference 11. We also present a 2-connected graph of circumference 11 in which all but one vertex are avoided by some longest cycle.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-019-02010-9