Edge-maximal θ_2k+1-free non-bipartite Hamiltonian graphs of odd order

Let 𝒢⁡(𝑛;𝜃_2⁢𝑘+1) denote the class of non-bipartite graphs on n vertices containing no 𝜃_2⁢𝑘+1-graph and 𝑓⁡(𝑛;𝜃_2⁢𝑘+1)=max⁡{ℰ⁡(𝐺):𝐺∈𝒢⁡(𝑛;𝜃_2⁢𝑘+1)}. Let ℋ⁡(𝑛;𝜃_2⁢𝑘+1) denote the class of non-bipartite Hamiltonian graphs on n vertices containing no 𝜃_2⁢𝑘+1-graph and ℎ⁡(𝑛;𝜃_2⁢𝑘+1)=max⁡{ℰ⁡(𝐺):𝐺∈ℋ⁡(𝑛;𝜃_2⁢𝑘+1)}. In this paper we determine ℎ⁡(𝑛;𝜃_2⁢𝑘+1) by proving that for sufficiently large odd n, ℎ⁡(𝑛;𝜃_2⁢𝑘+1)≤⌊(𝑛−2⁢𝑘+3)24⌋+2⁢𝑘−3. Furthermore, the bound is best possible. Our results confirm the conjecture made by Bataineh in 2007.

Other Information

Published in: AKCE International Journal of Graphs and Combinatorics
License: http://creativecommons.org/licenses/by/4.0/
See article on publisher's website: https://dx.doi.org/10.1080/09728600.2022.2145922