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

Abstract

Let $\mathcal{G}(n;{\theta }_{2k+1})$ denote the class of non-bipartite graphs on n vertices containing no ${\theta }_{2k+1}$-graph and $f(n;{\theta }_{2k+1})=\max \{\mathcal{E}(G):G\in \mathcal{G}(n;{\theta }_{2k+1})\}.$ Let $\mathcal{H}(n;{\theta }_{2k+1})$ denote the class of non-bipartite Hamiltonian graphs on n vertices containing no ${\theta }_{2k+1}$-graph and $h(n;{\theta }_{2k+1})=\max \{\mathcal{E}(G):G\in \mathcal{H}(n;{\theta }_{2k+1})\}.$ In this paper we determine $h(n;{\theta }_{2k+1})$ by proving that for sufficiently large odd n, $h(n;{\theta }_{2k+1})\le \lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3.$ Furthermore, the bound is best possible. Our results confirm the conjecture made by Bataineh in 2007.

Keywords:

• Ramsey number
• theta graph
• complete graph

MSC:

• 05C55
• 05C35

1. Introduction

We consider the graph H to be finite simple graph. The vertices and edges of H are denoted by V(H) and E(H), respectively. Moreover, v(H) (the order of H, that is, the number of vertices) and $\mathcal{E}(H)$ (the size of H, that is, the number of edges) denote the cardinalities of these sets, respectively. We denote by the cycle C_n having n vertices $v_1,v_2,\dots ,v_n$ and the edges $v_1{v}_2,v_2{v}_3,\dots ,v_{n-1}{v}_n$ and $v_n{v}_1.$ A cycle C is called even (or odd) if it has even (or odd) length. It is well known that a graph G is bipartite if and only if G contains no odd cycle. Let C be a cycle in a graph G. An edge joining two non adjacent vertices of C is called a chord of C. We say H has θ_k-graph if H has a cycle C of length k with a chord. The degree of a vertex $u\in H,$ denoted by $d_H(u),$ is the number of vertices in H adjacent to u. The neighbor set of a vertex u of H in a subgraph A of H, denoted by $N_A(u),$ consists of the vertices of A adjacent to u; we write $d_A(u)=|N_A(u)|.$ For vertex disjoint subgraphs H₁ and H₂ of H we let $E(H_1,H_2)=\{xy\in E(H):x\in V(H_1),y\in V(H_2)\}$ and $\mathcal{E}(H_1,H_2)=|E(H_1,H_2)|.$ For a subset Q of the vertex set of H, $H[Q]$ is defind to be the subgraph of H with vertex set Q and edge set consisting of all edges of H that joins vertices of Q, For a proper subgraph A of H we write $H[V(A)]$ and $H-V(A)$ simply as $H[A]$ and H – A, respectively.

Let n be a positive integer and $\mathcal{F}$ be a set of graphs. The Turán Type Extremal Problem is the problem of determine the maximum number of edges in an $\mathcal{F}$ -free graph on n vertices (see [19]). Furthermore, find the set consisting of all the so called extremal graphs, that is, the $\mathcal{F}$-free graphs on n vertices with the maximum number of edges is attained. When $\mathcal{F}$ consists of only one graph F we simply write F-free graph on n vertices

In this paper, the Turán-type extremal problem is considered, where the θ-graph is the forbidden subgraph in a Hamiltonian graphs. Also, we consider a non-bipartite Hamiltonian graphs because a bipartite graph does not contain odd θ-graph. The class of non-bipartite F-free graphs on n vertices is denoted by $\mathcal{G}(n;F)$ and $f(n;F)=\max \{\mathcal{E}(G):G\in \mathcal{G}(n;F)\}.$ Moreover, $\mathcal{H}(n;F)$ denotes to the subclass of $\mathcal{G}(n;F)$ consisting of Hamiltonian graphs in $\mathcal{G}(n;F).$ We write $h(n;F)=\max \{\mathcal{E}(G):G\in \mathcal{H}(n;F)\}.$

One of the important problems in extremal graph theory is to determine the values of $f(n;F)$ and $h(n;F).$ Also, characterize the extremal graphs of $\mathcal{G}(n;F)$ and $\mathcal{H}(n;F)$ where $f(n;F)$ and $h(n;F)$ are attained. A number of authors [2, 10, 14, 17] studied the edge maximal graphs of $\mathcal{G}(n;C_r).$ Bondy [7] and [8] proved that a Hamiltonian graph G on n vertices without a cycle of length r has at most $\frac{n^2}{4}$ edges with equality holding if and only if n is even and r is odd. Häggkvist et al. [13] proved that $f(n;C_r)\le \lfloor \frac{{(n-1)}^2}{4}\rfloor +1$ for all r. This result is sharp only for r = 3. Jia [17] conjectured that $f(n;C_{2r+1})\le \lfloor \frac{{(n-2)}^2}{4}\rfloor +3$ for $n\ge 4k+2.$ Bataineh [2] positively confirmed the above conjecture for $n\ge 36k.$ In the same work, he conjectured that for $k\ge 3,f(n;{\theta }_{2r+1})\le \lfloor \frac{{(n-2)}^2}{4}\rfloor +3.$ Jaradat et al. [15] and Bataineh et al. [5] and [6] confirmed the conjecture for lage n. Further, Bataineh et al. [4] proved that $f(n;{\theta }_5)\le \lfloor \frac{{(n-1)}^2}{4}\rfloor +1.$

Moon [18] proved that, if G contains no wheels, then $\mathcal{E}(G)\le \lfloor n^2/4\rfloor +\lfloor (n+1)/4\rfloor .$ Furthermore, he characterized the extremal graphs. In recent years, several authors reported results on wheels see [1, 4, 11, 12].

The problem of interest is the determination of $h(n;F)$ and the corresponding extremal graphs. In particular, the edge-maximal graphs of $\mathcal{H}(n;C_r)$ have been studied by a number of authors such as Hendry and Brandt [14] and Jia [17]. Jia, conjectured that for large odd n, $$h(n;C_{2k+1})\le \frac{{(n-2k+1)}^2}{4}+g(k),$$ where g(k) is a polynomial of k. Recently, Bataineh (2007) positively confirmed the above conjecture for $n>(4k+2)(4k^2+10k),$ where $k\ge 3.$ Moreover, Bataineh [2] post the following conjecture:

Conjecture 1. For odd $n\ge 4k+4,h(n,{\theta }_{2k+1})\le \frac{{(n-2k+3)}^2}{4}+2k-3,$ where $k\ge 3.$

In [3] and [16], Bataineh et al. and Jaradat et al., respectively, confirmed the conjecture for k = 3. In this paper we establish the above conjecture by proving that for sufficiently large odd n, $$h(n;{\theta }_{2k+1})\le \frac{{(n-2k+3)}^2}{4}+2k-3.$$ Furthermore, the bound is best possible.

2. Main results

The following results will be used frequently in the sequel:

Theorem 1.

[15] For positive integers n and k, let G be a graph on $n\ge 6k+3$ vertices which has no ${\theta }_{2k+1}$ as a subgraph, then $$\mathcal{E}(G)\le \lfloor \frac{n^2}{4}\rfloor .$$

Theorem 2.

[2] Let ${\vartheta }_k=\left\{{\theta }_4\right\}\cup \{{\theta }_5,{\theta }_7,\dots ,{\theta }_{2k+1}\}$. For $k\ge 5$ and large n, we have $$h(n,{\vartheta }_k)=\frac{{(n-2k+3)}^2}{4}+2k-3.$$

Theorem 3.

[9] Let $F_k=\{C_{2i+1}:1\le i\le k$. For $k\ge 2$ and $n\ge 3k+1$, then $$f(n,F_k)=\frac{{(n-2k+1)}^2}{4}+2k-1.$$

Theorem 4.

[2] Let $k\ge 3$ be a positive integer and $H\in \mathcal{H}(n;C_{2k+1})$. Then for $n>(4k+2)(4k^2+10k),$ $$h(n;C_{2k+1})=\{\begin{array}{cc}\frac{{(n-2k+1)}^2}{4}+4k-3,\hfill & \mathit{for}n\mathit{odd}\hfill \\ \frac{{(n-2k)}^2}{4}+4k+1,\hfill & \mathit{for}n\mathit{even}\hfill \end{array}$$

Now, we are ready to prove our result which confirm the conjecture.

For n odd, let ${\mathcal{G}}_{n,k}$ be the graph obtained from ${\overline{K}}_{\frac{n-2k+3}{2}}\vee {\overline{K}}_{\frac{n-2k+3}{2}}$ by replacing the edge $y_1{y}_2\in {\overline{K}}_{\frac{n-2k+3}{2}}\vee {\overline{K}}_{\frac{n-2k+3}{2}},$ by the path $y_1,w_2,\dots ,w_{2k-2},y_2$ with the vertices $w_2,w_3,\dots ,w_{2k-2}$ being all new vertices. Observe that ${\mathcal{G}}_{n,k}\in \mathcal{H}(n;{\vartheta }_k)$ and it contains $\frac{{(n-2k+3)}^2}{4}+2k-3$ edges. Thus, we have established that a graph $H\in \mathcal{H}(n;{\vartheta }_k)$ and $$\mathcal{E}(H)\ge \frac{{(n-2k+3)}^2}{4}+2k-3.$$

Theorem 5.

For positive integer $k\ge 5$ and for $n\ge 14k^2$, we have $$h(n;{\theta }_{2k+1})=\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3.$$

Proof.

By the above inequality, it is sufficient to prove that $$h(n;{\theta }_{2k+1})\le \lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3.$$

Let $k\ge 5$ and let $H\in \mathcal{H}(n;{\theta }_{2k+1}).$ Let A be the set of vertices in H such that the degree of each vertex less than or equal $14k-7.$ Let $\left|A\right|=r.$ We have, $$\begin{array}{cc}\mathcal{E}(H)\hfill & =\mathcal{E}(H-A)+\mathcal{E}(H-A,A)+\mathcal{E}(A)\hfill \\ \hfill & \le \lfloor \frac{{(n-r)}^2}{4}\rfloor +r(14k-7).\hfill \end{array}$$ For $n\ge 14k^2,$ the maximum for the right hand side when $r\ge 2k+4$ is at $r=2k+4.$ Thus, $$\mathcal{E}(H)\le \lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3.$$ Now, we consider $r\le 2k+3.$ If H – A is a bipartite graph with bipartition X and Y, then $\left|X\right|,\left|Y\right|\ge 12k-9$ ($\delta (H-A)\ge 14k-6$) and $\left|X\right|+\left|Y\right|\ge n-(2k+4)\ge 40k.$ Since H does not contain ${\theta }_{2k+1},$ then any vertex in A is adjacent to vertices in A and one partition X or Y. Since H is Hamiltonian and $\Delta (A)\le 14k-7,$ then there is a vertex u in A such that this vertex is adjacent to part of the vertices of X or Y. Therefor, $(H-A)\cup \left\{u\right\}$ is a non-bipartite graph. Moreover, this vertex does not effect the proof of the cases below. Thus, we consider H – A is a non-bipartite graph. To complete the proof, we consider two cases as follows:

Case 1.

$W=H-A$ contains θ-graph of order less than $2k+1.$ Let $3\le j<k$ be the maximum positive integer such that ${\theta }_{2j+1}$ is in W. The chord on ${\theta }_{2j+1}$ divided ${\theta }_{2j+1}$ onto two circles. Now, since $j\ge 3,$ then we choose $\{x_1,x_2,x_3,x_4,x_5\}$ on one circle. Also, if $u\in N_{W-{\theta }_{2j+1}}(x_i)\cap N_{W-{\theta }_{2j+1}}(x_2),$ i = 2, 4, assume that i = 2, then $(N_{W-{\theta }_{2j+1}}(x_3)-\{u\})\cap (N_{W-{\theta }_{2j+1}}(x_4)-\{u\})=(N_{W-{\theta }_{2j+1}}(x_2)-\{u\})\cap (N_{W-{\theta }_{2j+1}}(x_1)-\{u\})=(N_{W-{\theta }_{2j+1}}(x_4)-\{u\})\cap (N_{W-{\theta }_{2j+1}}(x_5)-\{u\})=\varphi$ as otherwise ${\theta }_{2(j+1)+1}$ is produced, a contradiction. Moreover, if $(N_{W-{\theta }_{2j+1}}(x_r))\cap (N_{W-{\theta }_{2j+1}}(x_3))=\varphi ,$ r = 2, 3 and $u\in N_{W-{\theta }_{2j+1}}(x_i)\cap N_{W-{\theta }_{2j+1}}(x_{i+1}),$ i = 1, 4, assume that i = 1, then $(N_{W-{\theta }_{2j+1}}(x_4)-\{u\})\cap (N_{W-{\theta }_{2j+1}}(x_5)-\{u\})=\varphi$ as otherwise ${\theta }_{2(j+1)+1}$ is produced, a contradiction. As a result, any vertex in $W-{\theta }_{2j+1}$ is adjacet to at most three vertice of $\{x_1,x_2,x_3,x_4,x_5\}$ except possibly for one vertex. Note that $\delta (W)\ge 14k-6.$ For $s=1,2,3,4,5,$ let A_s be a set that consist of $4k-2$ neighbors of x_s in $W-{\theta }_{2j+1}$ selected so that $A_s\cap A_t=\varphi$ for $t\ne s.$ Figure 1.2 depict the situation. Let $T=W[x_1,x_2,\dots ,x_j,\dots ,x_{2j+1},A_1,A_2,A_3,A_4,A_5]$ and $R=W-T.$ Note that by Theorem 1 we have $$\mathcal{E}(R)\le \lfloor \frac{{(n-r-(20k+2j-9))}^2}{4}\rfloor$$ and $$\mathcal{E}(T)\le \lfloor \frac{{(20k+2j-9)}^2}{4}\rfloor .$$

So we want to find $\mathcal{E}(R,T).$ Let $u\in V(R).$ Then we have the following observations:

• If u is adjacent to a vertex in A₁ say a₁, then we have the following:

  1. If u is adjacent to a vertex in A₃ say a₃, then the trail $x_1{x}_{2j+1}{x}_{2j}$ $\cdots x_4{x}_3{a}_{3}u{a}_1{x}_1{x}_{2j}$ forms ${\theta }_{2(j+1)+1},$ a contradiction since j is the maximum.

  2. If u is adjacent to x₂, then the trail $x_1{x}_{2j+1}{x}_{2j}{x}_{2j-1}\cdots x_3{x}_{2}u{a}_1{x}_1{x}_2$ forms ${\theta }_{2(j+1)+1},$ a contradiction since j is the maximum.

  3. If u is adjacent to $x_{2j+1},$ then the trail $$ forms ${\theta }_{2(j+1)+1},$ a contradiction since j is the maximum.

  4. If u is adjacent to a vertex in A₂ say a₂ and to a vertex in A₅ say a₅, then any vertex $v\in V(R-\{u\})$ can not be adjacent to a₁ and a₂ or a₂ and a₅ at the same time as otherwise ${\theta }_{2(j+1)+1}$ is produced, a contradiction.

• If u is adjacent to a vertex in A₂ say a₂, then we can notice the following:

  1. u is not adjacent to any vertex in A₄.

  2. u is not adjacent to any vertex in $\{x_1,x_3\}.$

• If u is adjacent to a vertex in A₃ say a₃, then we can notice the following:

  1. u is not adjacent to any vertex in A_s, s = 1, 5.

  2. u is not adjacent to any vertex in $\{x_2,x_4\}.$

• If u is adjacent to a vertex in A₄ say a₄, then we can notice the following:

  1. u is not adjacent to any vertex in A₂.

  2. u is not adjacent to any vertex in $\{x_3,x_5\}.$

• If u is adjacent to a vertex in A₅ say a₅, then we can notice the following:

  1. u is not adjacent to any vertex in A_s, s = 3.

  2. u is not adjacent to any vertex in $\{x_4,x_6\}.$

Taking in consideration the above observations, we have $$\mathcal{E}(R,T)\le (8k+2j-5)(n-r-(20k+2j-9))+8k-4.$$ Consequently, we have $$\begin{array}{cc}\mathcal{E}(H)\hfill & =\mathcal{E}(R)+\mathcal{E}(R,T)+\mathcal{E}(T)+r(14k-7)\hfill \\ \hfill & \le \lfloor \frac{{(n-r-(20k+2j-9))}^2}{4}\rfloor +(8k+2j-5)\times \hfill \\ \hfill & (n-r-(20k+2j-9))+8k-4+r(14k-7)+\lfloor \frac{{(20k+2j-9)}^2}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{-8j^2+j(-64k+4n+40)+160k^2-8kn+n^2-2n-34}{4}\rfloor .\hfill \end{array}$$ Define $$g(j)=\frac{1}{4}(-8j^2+j(-64k+4n+40)+160k^2-8kn+n^2-2n-34),$$ for $3\le j<k.$ Note that, g is an increasing function with respect to j. Therefore, g has its maximum at $j=k-1.$ Thus $$\begin{array}{cc}\mathcal{E}(H)\hfill & \le g(j)\hfill \\ \hfill & \le \lfloor \frac{n^2-4kn-6n+88k^2-120k-82}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{{(n-2k+3)}^2-12n+84k^2+132k-91}{4}\rfloor \hfill \\ \hfill & <\lfloor \frac{(n-2k+3)}{4}\rfloor +\alpha (n)\hfill \end{array}$$ where $$\alpha (n)=\lfloor \frac{-12n+84k^2+132k-91}{4}\rfloor .$$

For $k\ge 5$ and $n\ge 9k^2$ odd, $\alpha (n)$ is negative and hence $$\mathcal{E}(H)<\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3$$ as required. Now we need to consider that there exist no $3\le j<k$ such that ${\theta }_{2j+1}$ is in H – A as a subgraph. So we have to consider two cases according the existing of θ₅-graph as a subgraph in H – A.

Subcase 1.

$W=H-A$ has θ₅-graph as a subgraph.

Let $x_1{x}_2{x}_3{x}_4{x}_5{x}_1{x}_4$ be θ₅-graph subgraph in W. Note that $\delta (W)\ge 14k-6.$ For i = 1, 2, 3, let A_i be a set that consist of $4k-4$ neighbors of x_i in W selected so that $A_i\cap A_j=\varphi$ for $i\ne j.$ Let $T_1=W[x_1,x_2,x_3,x_4,x_5,A_1,A_2,A_3]$ and $R_1=W-T_1,$ Figure 1.3 depict the situation. Let $u\in V(R_1).$ If u is joined to a vertex in one of the sets A₁, A₂ and A₃, then u cannot be joined to a vertex in the other two sets as otherwise, H would have a θ₇-graph as a subgraph. Also, if u is joined to a vertex in A_i for some i = 1, 2, 3, then u cannot be joined to $x_{i+1}$ and $x_{i-1},$ otherwise, H would have a θ₇-graph as a subgraph. Thus, $\mathcal{E}(\{u\},T_1)\le 4k-1.$ Consequently, we have $$\mathcal{E}(R_1,T_1)\le (4k-1)(n-r-(12k-7)).$$ Also, by Theorem 1 we have $$\mathcal{E}(R_1)\le \lfloor \frac{{(n-r-(12k-7))}^2}{4}\rfloor$$ and $$\mathcal{E}(T_1)\le \lfloor \frac{{(12k-7)}^2}{4}\rfloor .$$ Consequently, we have $$\begin{array}{cc}\mathcal{E}(H)\hfill & =\mathcal{E}(R_1)+\mathcal{E}(R_1,T_1)+\mathcal{E}(T_1)+r(14k-7)\hfill \\ \hfill & \le \lfloor \frac{{(n-r-(12k-7))}^2}{4}\rfloor +(4k-1)(n-r-(12k-7))+r(14k-7)+\lfloor \frac{{(12k-7)}^2}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{n^2-8nk+10n+96k^2-176k+70}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{{(n-2k+3)}^2-4nk+4n+92k^2-164k+61}{4}\rfloor \hfill \\ \hfill & <\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +\alpha (n)\hfill \end{array}$$ where $$\alpha (n)=\lfloor \frac{(n(-4k+4)+92k^2-164k+61}{4}\rfloor .$$

For $k\ge 5$ and $n\ge 9k^2$ odd, $\alpha (n)$ is negative. Therefore, $$\mathcal{E}(H)<\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3$$ as required.

Subcase 2.

$W=H-A$ has no θ₅-graph as a subgraph. Consider the case that W contains θ₄-graph. Let $x_1{x}_2{x}_3{x}_4$ be θ₄ with $x_2{x}_4$ the chord. Note that $\delta (W)\ge 14k-6.$ For i = 1, 2, 3, let A_i be a set that consist of $4k-4$ neighbors of x_i in W selected so that $A_i\cap A_j=\varphi$ for $i\ne j.$ Let $T_2=W[x_1,x_2,x_3,x_4,A_1,A_2,A_3]$ and $R_2=W-T_2,$ Figure 1.4 depict the situation. Let $u\in V(R_2).$ If u is joined to a vertex in one of the sets A₁, A₂ and A₃, then u cannot be joined to a vertex in the other two sets as otherwise, H would have a θ₇-graph as a subgraph. Also, if u is joined to a vertex in A_i for some i = 1, 2, 3, then u cannot be joined to $x_{i+1}$ and $x_{i-1},$ otherwise, W would have a θ₅-graph as a subgraph. Thus, $\mathcal{E}(\{u\},T_2)\le 4k-2.$ Consequently, we have $$\mathcal{E}(R_2,T_2)\le (4k-2)(n-r-(12k-8)).$$ Also, by Theorem 1 we have $$\mathcal{E}(R_2)\le \lfloor \frac{{(n-r-(12k-8))}^2}{4}\rfloor$$ and $$\mathcal{E}(T_2)\le \lfloor \frac{{(12k-8)}^2}{4}\rfloor .$$

Consequently, we have $$\begin{array}{cc}\mathcal{E}(H)\hfill & =\mathcal{E}(R_2)+\mathcal{E}(R_2,T_2)+\mathcal{E}(T_2)+r(14k-7)\hfill \\ \hfill & \le \lfloor \frac{{(n-r-(12k-8))}^2}{4}\rfloor +(4k-2)(n-r-(12k-8))+r(14k-7)+\lfloor \frac{{(12k-8)}^2}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{n^2-8nk+8n+96k^2-160k+64}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{{(n-2k+3)}^2-4nk+2n+92k^2-148k+55}{4}\rfloor \hfill \\ \hfill & <\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +\alpha (n)\hfill \end{array}$$ where $$\alpha (n)=\lfloor \frac{(n(-4k+2)+92k^2-148k+55}{4}\rfloor .$$ For $k\ge 5$ and $n\ge 9k^2$ odd, $\alpha (n)$ is negative. Therefore, $$\mathcal{E}(H)<\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3$$ as required.

Case 2.

H – A contains no θ₄ and ${\theta }_{2j+1},2\le j\le k-1.$

Subcase 3.

H – A does not contain $C_{2j+1}$ for some $1\le j\le k.$ Apply the same arguments in Case 1 on $C_{2(j-1)+1},$ we get the required result.

Subcase 4.

$W=H-A$ does not contain $C_{2k+1}.$ We consider W does not contain $C_{2j+1}$ for all $1\le j\le k-1$ as otherwise we get Case 3. Then by Theorem 4 $$\mathcal{E}(W)\le \lfloor \frac{{(n-r-2k+1)}^2}{4}\rfloor +2k-1.$$

Therefore, $$\begin{array}{cc}\mathcal{E}(H)\hfill & \le \lfloor \frac{{(n-r-2k+1)}^2}{4}\rfloor +2k-1+r(14k-7)\hfill \\ \hfill & \le \lfloor \frac{4k^2-4kn+60kr+4k+n^2-2nr+2n+r^2-30r-3}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{{(n-2k+3)}^2+16k-4n-12}{4}\rfloor \hfill \\ \hfill & <\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +\alpha (n)\hfill \end{array}$$ where $$\alpha (n)=\lfloor \frac{16k-4n-12}{4}\rfloor .$$

For $k\ge 5$ and odd $n\ge 9k^2,\alpha (n)$ is negative. Therefore, $$\mathcal{E}(H)<\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3$$ as required.

Subcase 5.

$W=H-A$ contains $C_{2k+1}=x_1{x}_2\cdots x_{2k+1}x)1.$ Let $R=W-C_{2k+1}.$ We have the following observations.

1. If $u\in R$ is adjacent to x_s, x_t and x_w, then the number of vertices between any two vertices is even as otherwise θ₄ or ${\theta }_{2j+1},2\le j\le k$ is produced.

2. If $u\in R,$ then u is adjacent to at most three vertices of the vertices of $C_{2k+1}.$

3. If $u\in R$ is adjacent to three vertices of the vertices of $C_{2k+1},$ then v is adjacent to at most two vertices of the vertices of $C_{2k+1}$ for any $v\in R-\left\{u\right\}$ as otherwise some θ-graph is produced.

As a result from the above observations, we have $$\begin{array}{cc}\mathcal{E}(H)\hfill & \le \lfloor \frac{{(n-r-2k-1-2)}^2}{4}\rfloor +2(n-r-2k-1)+1+r(14k-7)\hfill \\ \hfill & \le \lfloor \frac{4k^2-4kn+60kr-12k+n^2-2nr+6n+r^2-34r-7}{4}\rfloor \hfill \\ \hfill & \le \lfloor \frac{{(n-2k+3)}^2+16k-4n}{4}\rfloor \hfill \\ \hfill & <\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +\alpha (n)\hfill \end{array}$$ where $$\alpha (n)=\lfloor \frac{16k-4n}{4}\rfloor .$$

For $k\ge 5$ and odd $n\ge 9k^2,\alpha (n)$ is negative. Therefore, $$\mathcal{E}(H)<\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3$$ as required.□

For the completeness we repost the following unsettled conjecture made by Bataineh in his Ph.D Theses [2] for the even n:

Conjecture 2.

For even $n\ge 4k+4,h(n,{\theta }_{2k+1})\le \frac{{(n-2k+2)}^2}{4}+2k,$ where $k\ge 3.$

It worths mentioning that in 2019, Bataineh et al. [4] confirmed the above conjecture for k = 3 with some other constraints on graphs.

3. Conclusion

In this paper, we considered the Turán-type extremal problem, where the θ-graph is the forbidden subgraph in a Hamiltonian graphs. Also, we consider a non-bipartite Hamiltonian graphs because a bipartite graph does not contain odd θ-graph. In fact, confirmed a conjecture made by Bataineh in [2] by proving that for large odd integer n and $k\ge 5,$ the maximum number of edges of a graph with n vertices that contains no $(2k+1)$-theta subgraph is equal to $\lfloor \frac{{(n-2k+3)}^2}{4}\rfloor +2k-3.$ Further, we restated the conjecture for even n.

Authors contributions

All authors contributed equally and significantly in writing this paper. All authors read and approved the final manuscript.

Acknowledgements

Open Access funding provided by the Qatar National Library.

Availability of data and material

Data sharing not applicable to this article as no data sets were generated or analysed during the current study.

Conflicts of interest

The authors declare that they have no conflict of interest.