Pancyclicity when each cycle must pass exactly k Hamilton cycle chords.

Journal article


Chaouche, FA, Rutherford, CG and Whitty, R (2015). Pancyclicity when each cycle must pass exactly k Hamilton cycle chords. Discussiones Mathematicae Graph Theory. 35 (3), pp. 533-539. https://doi.org/10.7151/dmgt.1818
AuthorsChaouche, FA, Rutherford, CG and Whitty, R
Abstract

It is known that Θ(log n) 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 1/k� on the growth rate.

Year2015
JournalDiscussiones Mathematicae Graph Theory
Journal citation35 (3), pp. 533-539
PublisherFaculty of Mathematics, Computer Science and Econometrics - University of Zielona Góra
ISSN1234-3099
Digital Object Identifier (DOI)https://doi.org/10.7151/dmgt.1818
Publication dates
Print30 Sep 2015
Publication process dates
Deposited19 Dec 2017
Accepted30 Sep 2015
Accepted author manuscript
License
File Access Level
Open
Permalink -

https://openresearch.lsbu.ac.uk/item/875yq

Download files


Accepted author manuscript
C:\Users\ruthercg\Desktop\1212.3633.pdf
License: CC BY-NC-ND 4.0
File access level: Open

  • 43
    total views
  • 53
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

Generalized pentagonal geometries
Forbes, A. and Rutherford, C. G. (2021). Generalized pentagonal geometries. Journal of Combinatorial Designs. https://doi.org/10.1002/jcd.21811
Some results on the structure and spectra of matrix-products
Rutherford, CG (2015). Some results on the structure and spectra of matrix-products. Linear Algebra and Its Applications. 474, pp. 192-212. https://doi.org/10.1016/j.laa.2015.02.008
P-matrices and signed digraphs
Banaji, M and Rutherford, CG (2010). P-matrices and signed digraphs. Discrete Mathematics. 311 (4), pp. 295-301. https://doi.org/10.1016/j.disc.2010.10.018
Covering radii are not matroid invariants
Britz, T. and Rutherford, C. (2005). Covering radii are not matroid invariants. 296 (1), pp. 117-120. https://doi.org/10.1016/j.disc.2005.03.002