Pancyclicity When Each Cycle Contains k Chords
For integers n ≥ k ≥ 2, let c(n, k) be the minimum number of chords that must be added to a cycle of length n so that the resulting graph has the property that for every l ∈ {k, k + 1, . . . , n}, there is a cycle of length l that contains exactly k of the added chords. Affif Chaouche, Rutherford, a...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2019-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2106 |
| _version_ | 1797704373197864960 |
|---|---|
| author | Taranchuk Vladislav |
| author_facet | Taranchuk Vladislav |
| author_sort | Taranchuk Vladislav |
| collection | DOAJ |
| description | For integers n ≥ k ≥ 2, let c(n, k) be the minimum number of chords that must be added to a cycle of length n so that the resulting graph has the property that for every l ∈ {k, k + 1, . . . , n}, there is a cycle of length l that contains exactly k of the added chords. Affif Chaouche, Rutherford, and Whitty introduced the function c(n, k). They showed that for every integer k ≥ 2, c(n, k) ≥ Ωk(n1/k) and they asked if n1/k gives the correct order of magnitude of c(n, k) for k ≥ 2. Our main theorem answers this question as we prove that for every integer k ≥ 2, and for sufficiently large n, c(n, k) ≤ k⌈n1/k⌉ + k2. This upper bound, together with the lower bound of Affif Chaouche et al., shows that the order of magnitude of c(n, k) is n1/k. |
| first_indexed | 2024-03-12T05:19:25Z |
| format | Article |
| id | doaj.art-1c0358f7466a47b7b17cccea85a511f4 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:19:25Z |
| publishDate | 2019-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-1c0358f7466a47b7b17cccea85a511f42023-09-03T07:47:22ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922019-11-0139486787910.7151/dmgt.2106dmgt.2106Pancyclicity When Each Cycle Contains k ChordsTaranchuk Vladislav0Department of Mathematics and Statistics, California State University, Sacramento, Sacramento, CAFor integers n ≥ k ≥ 2, let c(n, k) be the minimum number of chords that must be added to a cycle of length n so that the resulting graph has the property that for every l ∈ {k, k + 1, . . . , n}, there is a cycle of length l that contains exactly k of the added chords. Affif Chaouche, Rutherford, and Whitty introduced the function c(n, k). They showed that for every integer k ≥ 2, c(n, k) ≥ Ωk(n1/k) and they asked if n1/k gives the correct order of magnitude of c(n, k) for k ≥ 2. Our main theorem answers this question as we prove that for every integer k ≥ 2, and for sufficiently large n, c(n, k) ≤ k⌈n1/k⌉ + k2. This upper bound, together with the lower bound of Affif Chaouche et al., shows that the order of magnitude of c(n, k) is n1/k.https://doi.org/10.7151/dmgt.2106pancyclicitychords05d9911b75 |
| spellingShingle | Taranchuk Vladislav Pancyclicity When Each Cycle Contains k Chords Discussiones Mathematicae Graph Theory pancyclicity chords 05d99 11b75 |
| title | Pancyclicity When Each Cycle Contains k Chords |
| title_full | Pancyclicity When Each Cycle Contains k Chords |
| title_fullStr | Pancyclicity When Each Cycle Contains k Chords |
| title_full_unstemmed | Pancyclicity When Each Cycle Contains k Chords |
| title_short | Pancyclicity When Each Cycle Contains k Chords |
| title_sort | pancyclicity when each cycle contains k chords |
| topic | pancyclicity chords 05d99 11b75 |
| url | https://doi.org/10.7151/dmgt.2106 |
| work_keys_str_mv | AT taranchukvladislav pancyclicitywheneachcyclecontainskchords |