- Tytuł:
- Pancyclicity When Each Cycle Contains k Chords
- Autorzy:
- Taranchuk, Vladislav
- Powiązania:
- https://bibliotekanauki.pl/articles/31343202.pdf
- Data publikacji:
- 2019-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
pancyclicity
chords - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 867-879
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł