Edge-maximal θ2k+1-free non-bipartite Hamiltonian graphs of odd order. Issue 3 (2nd September 2022)

• Record Type: Journal Article
• Authors: Jaradat, M. M. M.; Baniabedalruhman, A.; Bataineh, M. S.; Jaradat, A. M. M.; Al-Rhayyel, A. A.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 19:Issue 3(2022)
• Page Start: 282
• Page End: 286
• Publication Date: 2022-09-02
• Subjects: Ramsey number -- theta graph -- complete graph; 05C55 -- 05C35
• DOI: 10.1080/09728600.2022.2145922
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: Let G ( n ; θ 2 k + 1 ) denote the class of non-bipartite graphs on n vertices containing no θ 2 k + 1 -graph and f ( n ; θ 2 k + 1 ) = max { E ( G ) : G ∈ G ( n ; θ 2 k + 1 ) } . Let H ( n ; θ 2 k + 1 ) denote the class of non-bipartite Hamiltonian graphs on n vertices containing no θ 2 k + 1 -graph and h ( n ; θ 2 k + 1 ) = max { E ( G ) : G ∈ H ( n ; θ 2 k + 1 ) } . In this paper we determine h ( n ; θ 2 k + 1 ) by proving that for sufficiently large odd n, h ( n ; θ 2 k + 1 ) ≤ ⌊ ( n − 2 k + 3 ) 2 4 ⌋ + 2 k − 3 . Furthermore, the bound is best possible. Our results confirm the conjecture made by Bataineh in 2007.