Edge-maximal <i>θ</i><sub>2k+1</sub>-free non-bipartite Hamiltonian graphs of odd order
<p dir="ltr">Let (;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>) denote the class of non-bipartite graphs on <i>n</i> vertices containing no <sub>2</sub><sub></sub><sub...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , , |
| Published: |
2022
|
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | <p dir="ltr">Let (;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>) denote the class of non-bipartite graphs on <i>n</i> vertices containing no <sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>-graph and (;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>)=max{ℰ():∈(;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>)}. Let ℋ(;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>) denote the class of non-bipartite Hamiltonian graphs on <i>n</i> vertices containing no <sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>-graph and ℎ(;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>)=max{ℰ():∈ℋ(;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>)}. In this paper we determine ℎ(;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>) by proving that for sufficiently large odd <i>n</i>, ℎ(;<sub>2</sub><sub></sub><sub></sub><sub>+</sub><sub>1</sub>)≤⌊(−2+3)24⌋+2−3. Furthermore, the bound is best possible. Our results confirm the conjecture made by Bataineh in 2007.</p><h2>Other Information</h2><p dir="ltr">Published in: AKCE International Journal of Graphs and Combinatorics<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1080/09728600.2022.2145922" target="_blank">https://dx.doi.org/10.1080/09728600.2022.2145922</a></p> |
|---|