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.
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
PublisherLondon South Bank University
Digital Object Identifier (DOI)doi:10.7151/dmgt.1818
Publication dates
Print30 Sep 2015
Publication process dates
Deposited19 Dec 2017
Accepted30 Sep 2015
Accepted author manuscript
License
CC BY-NC-ND 4.0
Permalink -

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

  • 0
    total views
  • 11
    total downloads
  • 0
    views this month
  • 6
    downloads this month

Related outputs

P-matrices and signed digraphs
Banaji, M and Rutherford, CG (2010). P-matrices and signed digraphs. Discrete Mathematics. 311 (4), pp. 295-301.
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.