Pancyclicity when each cycle must pass exactly K Hamilton cycle chords

Fatima Affif Chaouche; Carrie G. Rutherford; Robin W. Whitty

doi:10.7151/dmgt.1818

Pancyclicity when each cycle must pass exactly K Hamilton cycle chords

Fatima Affif Chaouche, Carrie G. Rutherford, Robin W. Whitty

London South Bank University

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

1 Citation (Scopus)

Abstract

It is known that θ(logn) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, θ(n) chords are required. A possibly 'intermediate' variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of Ω(n¹/^k) on the growth rate.

Original language	English
Pages (from-to)	533-539
Number of pages	7
Journal	Discussiones Mathematicae Graph Theory
Volume	35
Issue number	3
DOIs	https://doi.org/10.7151/dmgt.1818 https://doi.org/10.7151/dmgt.1818
Publication status	Published - 30 Sept 2015

Keywords

Extremal graph theory
Hamilton cycle
Pancyclic graph

Access to Document

10.7151/dmgt.1818
10.7151/dmgt.1818Licence: CC BY-NC-ND 4.0

Cite this

@article{7d588015e6d3419c85f799f249cf5da1,

title = "Pancyclicity when each cycle must pass exactly K Hamilton cycle chords",

abstract = "It is known that θ(logn) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, θ(n) chords are required. A possibly 'intermediate' variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of Ω(n1/k) on the growth rate.",

keywords = "Extremal graph theory, Hamilton cycle, Pancyclic graph",

author = "Chaouche, \{Fatima Affif\} and Rutherford, \{Carrie G.\} and Whitty, \{Robin W.\}",

year = "2015",

month = sep,

day = "30",

doi = "10.7151/dmgt.1818",

language = "English",

volume = "35",

pages = "533--539",

journal = "Discussiones Mathematicae Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "3",

}

TY - JOUR

T1 - Pancyclicity when each cycle must pass exactly K Hamilton cycle chords

AU - Chaouche, Fatima Affif

AU - Rutherford, Carrie G.

AU - Whitty, Robin W.

PY - 2015/9/30

Y1 - 2015/9/30

N2 - It is known that θ(logn) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, θ(n) chords are required. A possibly 'intermediate' variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of Ω(n1/k) on the growth rate.

AB - It is known that θ(logn) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, θ(n) chords are required. A possibly 'intermediate' variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of Ω(n1/k) on the growth rate.

KW - Extremal graph theory

KW - Hamilton cycle

KW - Pancyclic graph

UR - https://www.scopus.com/pages/publications/84942080276

U2 - 10.7151/dmgt.1818

DO - 10.7151/dmgt.1818

M3 - Article

SN - 1234-3099

VL - 35

SP - 533

EP - 539

JO - Discussiones Mathematicae Graph Theory

JF - Discussiones Mathematicae Graph Theory

IS - 3

ER -

Pancyclicity when each cycle must pass exactly K Hamilton cycle chords

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this