On Hamiltonian Cycles in Claw-Free Cubic Graphs
We show that every claw-free cubic graph of order n at least 8 has at most 2⌊n4⌋{2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs.
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2249 |
| _version_ | 1827844634726891520 |
|---|---|
| author | Mohr Elena Rautenbach Dieter |
| author_facet | Mohr Elena Rautenbach Dieter |
| author_sort | Mohr Elena |
| collection | DOAJ |
| description | We show that every claw-free cubic graph of order n at least 8 has at most 2⌊n4⌋{2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs. |
| first_indexed | 2024-03-12T08:44:42Z |
| format | Article |
| id | doaj.art-373a713b522f4c52bc1f11bd75b29ccc |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:42Z |
| publishDate | 2022-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-373a713b522f4c52bc1f11bd75b29ccc2023-09-02T16:29:34ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-02-0142130931310.7151/dmgt.2249On Hamiltonian Cycles in Claw-Free Cubic GraphsMohr Elena0Rautenbach Dieter1Institute of Optimization and Operations Research, Ulm University, GermanyInstitute of Optimization and Operations Research, Ulm University, GermanyWe show that every claw-free cubic graph of order n at least 8 has at most 2⌊n4⌋{2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs.https://doi.org/10.7151/dmgt.2249hamiltonian cycleclaw-free graphcubic graph05c70 |
| spellingShingle | Mohr Elena Rautenbach Dieter On Hamiltonian Cycles in Claw-Free Cubic Graphs Discussiones Mathematicae Graph Theory hamiltonian cycle claw-free graph cubic graph 05c70 |
| title | On Hamiltonian Cycles in Claw-Free Cubic Graphs |
| title_full | On Hamiltonian Cycles in Claw-Free Cubic Graphs |
| title_fullStr | On Hamiltonian Cycles in Claw-Free Cubic Graphs |
| title_full_unstemmed | On Hamiltonian Cycles in Claw-Free Cubic Graphs |
| title_short | On Hamiltonian Cycles in Claw-Free Cubic Graphs |
| title_sort | on hamiltonian cycles in claw free cubic graphs |
| topic | hamiltonian cycle claw-free graph cubic graph 05c70 |
| url | https://doi.org/10.7151/dmgt.2249 |
| work_keys_str_mv | AT mohrelena onhamiltoniancyclesinclawfreecubicgraphs AT rautenbachdieter onhamiltoniancyclesinclawfreecubicgraphs |