# Two Sufficient Conditions for Hamilton and Dominating Cycles

Authors: Zh. G. Nikoghosyan
Journal: International Journal of Mathematics and Mathematical Sciences
 (2012)

---

## Abstract

We prove that ifG is a 2-connect graph of size q (the number of edges) and minimum degree δ with δ≥2q/3+ϵ/12-1/2, where ϵ=11 when δ=2 and ϵ=31 when δ≥3, then each longest cycle in G is a dominating cycle. The exact analog of this theorem for Hamilton cycles follows easily from two known results according to Dirac and Nash-Williams: each graph with δ≥q+5/4-1/2 is hamiltonian. Both results are sharp in all respects.


---

## Body

## 1. Introduction

Only finite undirected graphs without loops or multiple edges are considered. We reserven, q, δ, and κ to denote the number of vertices (order), the number of edges (size), the minimum degree, and the connectivity of a graph, respectively. A graph G is hamiltonian if G contains a hamiltonian cycle, that is, a cycle of length n. Further, a cycle C in G is called a dominating cycle if the vertices in G∖C are mutually nonadjacent. A good reference for any undefined terms is [1].The following two well-known theorems provide two classic sufficient conditions for Hamilton and dominating cycles by linking the minimum degreeδ and order n.Theorem A (see [2]).
Every graph withδ≥(1/2)n is hamiltonian.Theorem B (see [3]).
IfG is a 2-connect graph with δ≥(1/3)(n+2), then each longest cycle in G is a dominating cycle.The exact analog of Theorem A that links the minimum degreeδ and size q easily follows from Theorem A and a particular result according to Nash-Williams [4] (see Theorem 1.1 below).Theorem 1.1.
Every graph is hamiltonian if(1.1)δ≥q+54-12.The hypothesis in Theorem1.1 is equivalent to q≤δ2+δ-1 and cannot be relaxed to q≤δ2+δ due to the graph K1+2Kδ consisting of two copies of Kδ+1 and having exactly one vertex in common. Hence, Theorem 1.1 is best possible.The main goal of this paper is to prove the exact analog of Theorem B for dominating cycles based on another similar relation betweenδ and q.Theorem 1.2.
LetG be a 2-connect graph with
(1.2)δ≥2q3+ϵ12-12,
where ϵ=11 when δ=2 and ϵ=31 when δ≥3. Then each longest cycle in G is a dominating cycle.To show that Theorem1.2 is sharp, suppose first that δ=2, implying that the hypothesis in Theorem 1.2 is equivalent to q≤8. The graph K1+2K2 shows that the connectivity condition κ≥2 in Theorem 1.2 cannot be relaxed by replacing it with κ≥1. The graph with vertex set {v1,v2,…,v8} and edge set
(1.3){v1v2,v2v3,v3v4,v4v5,v5v6,v6v1,v1v7,v7v8,v8v4}
shows that the size bound q≤8 cannot be relaxed by replacing it with q≤9. Finally, the graph K2+3K1 shows that the conclusion “each longest cycle in G is a dominating cycle” cannot be strengthened by replacing it with “G is hamiltonian.” Analogously, we can use K1+2Kδ, K2+3Kδ-1, and Kδ+(δ+1)K1, respectively, to show that Theorem 1.2 is sharp when δ≥3. So, Theorem 1.2 is best possible in all respects.To prove Theorems1.1 and 1.2, we need two known results, the first of which is belongs Nash-Williams [4].Theorem C (see [4]).
Ifδ=(n-1)/2, then either G is hamiltonian or G=K1+2Kδ, or G=K¯δ+1+Gδ, where Gδ denote an arbitrary graph on δ vertices.The next theorem provides a lower bound for the length of a longest cycle in 2-connected graphs according to Dirac [2].Theorem D (see [2]).
Every 2-connected graph either has a hamiltonian cycle or has a cycle of length at least2δ.


## 2. Notations and Preliminaries

The set of vertices of a graphG is denoted by V(G) and the set of edges by E(G). For S, a subset of V(G), we denote by G∖S the maximum subgraph of G with vertex set V(G)∖S. We write G[S] for the subgraph of G induced by S. For a subgraph H of G, we use G∖H short for G∖V(H). The neighborhood of a vertex x∈V(G) will be denoted by N(x). Set d(x)=|N(x)|. Furthermore, for a subgraph H of G and x∈V(G), we define NH(x)=N(x)∩V(H) and dH(x)=|NH(x)|.A simple cycle (or just a cycle)C of length t is a sequence v1v2⋯vtv1 of distinct vertices v1,…,vt with vivi+1∈E(G) for each i∈{1,…,t}, where vt+1=v1. When t=2, the cycle C=v1v2v1 on two vertices v1,v2 coincides with the edge v1v2, and when t=1, the cycle C=v1 coincides with the vertex v1. So, all vertices and edges in a graph can be considered as cycles of lengths 1 and 2, respectively.Paths and cycles in a graphG are considered as subgraphs of G. If Q is a path or a cycle, then the length of Q, denoted by |Q|, is |E(Q)|. We write Q with a given orientation by Q→. For x,y∈V(Q), we denote by xQ→y the subpath of Q in the chosen direction from x to y. For x∈V(Q), we denote the hth successor and the hth predecessor of x on Q→ by x+h and x-h, respectively. We abbreviate x+1 and x-1 by x+ and x-, respectively.Special Definitions
LetG be a graph, C a longest cycle in G, and P=xP→y a longest path in G∖C of length p¯≥0. Let ξ1,ξ2,…,ξs be the elements of NC(x)∪NC(y) occurring on C in a consecutive order. Set
(2.1)Ii=ξiC→ξi+1,Ii*=ξi+C→ξi+1-(i=1,2,…,s),
where ξs+1=ξ1.(∗1)
We callI1,I2,…,Is elementary segments on C created by NC(x)∪NC(y).(∗2)
We call a pathL=zL→w an intermediate path between two distinct elementary segments Ia and Ib if
(2.2)z∈V(Ia*),w∈V(Ib*),V(L)∩V(C∪P)={z,w}.(∗3)
The set of all intermediate paths between elementary segmentsIi1,Ii2,…,Iit will be denoted by Υ(Ii1,Ii2,…,Iit).Lemma 2.1.
LetG be a graph, C a longest cycle in G, and P=xP→y a longest path in G∖C of length p¯≥1. If |NC(x)|≥2, |NC(y)|≥2 and NC(x)≠NC(y), then
(2.3)|C|≥{3δ+max{σ1,σ2}-1≥3δ,ifp¯=1,max{2p¯+8,4δ-2p¯},ifp¯≥2,
where σ1=|NC(x)∖NC(y)| and σ2=|NC(y)∖NC(x)|.Lemma 2.2.
LetG be a graph, C a longest cycle in G, and P=xP→y a longest path in G∖C of length p¯≥0. If NC(x)=NC(y), |NC(x)|≥2 and Ia, Ib are elementary segments induced by NC(x)∪NC(y), then(a1) ifL is an intermediate path between Ia and Ib, then
(2.4)|Ia|+|Ib|≥2p¯+2|L|+4,(a2) ifΥ(Ia,Ib)⊆E(G) and |Υ(Ia,Ib)|=i  for some i∈{1,2,3}, then
(2.5)|Ia|+|Ib|≥2p¯+i+5.Lemma 2.3.
LetG be a graph, S a cut set in G, and H a connected component of G∖S of order h. Then
(2.6)qH≥h(2δ-h+1)2,
where qH=|{xy∈E(G):{x,y}∩V(H)≠∅}|.Lemma 2.4.
LetG be a 2-connect graph. If δ≥(n-2)/3, then either
(2.7)q≥{9whenδ=2,3(δ-1)(δ+2)2whenδ≥3,
or each longest cycle in G is a dominating cycle.


## 3. Proofs

Proof of Lemma2.1.
Put(3.1)A1=NC(x)∖NC(y),A2=NC(y)∖NC(x),M=NC(x)∩NC(y).
By the hypothesis, NC(x)≠NC(y), implying that
(3.2)max{|A1|,|A2|}≥1.
Let ξ1,ξ2,…,ξs be the elements of NC(x)∪NC(y) occuring on C in a consecutive order. Put Ii=ξiC→ξi+1(i=1,2,…,s), where ξs+1=ξ1. Clearly, s=|A1|+|A2|+|M|. Since C is extreme, |Ii|≥2(i=1,2,…,s). Next, if {ξi,ξi+1}∩M≠∅ for some i∈{1,2,…,s}, then |Ii|≥p¯+2. Further, if either ξi∈A1, ξi+1∈A2 or ξi∈A2, ξi+1∈A1, then again |Ii|≥p¯+2.
Case  1. (p¯=1).
Case  1.1 (|Ai|≥1(i=1,2)). It follows that among I1,I2,…,Is there are |M|+2 segments of length at least p¯+2. Observing also that each of the remaining s-(|M|+2) segments has a length at least 2, we have
(3.3)|C|≥(p¯+2)(|M|+2)+2(s-|M|-2)=3(|M|+2)+2(|A1|+|A2|-2)=2|A1|+2|A2|+3|M|+2.
Since|A1|=d(x)-|M|-1 and |A2|=d(y)-|M|-1,
(3.4)|C|≥2d(x)+2d(y)-|M|-2≥3δ+d(x)-|M|-2.
Recalling that d(x)=|M|+|A1|+1, we get
(3.5)|C|≥3δ+|A1|-1=3δ+σ1-1.
Analogously, |C|≥3δ+σ2-1. So,
(3.6)|C|≥3δ+max{σ1,σ2}-1≥3δ.Case  1.2 (either |A1|≥1, |A2|=0 or |A1|=0, |A2|≥1). Assume without loss of generality that |A1|≥1 and |A2|=0, that is, |NC(y)|=|M|≥2 and s=|A1|+|M|. Hence, among I1,I2,…,Is there are |M|+1 segments of length at least p¯+2=3. Taking into account that each of the remaining s-(|M|+1) segments has a length at least 2 and |M|+1=d(y), we get
(3.7)|C|≥3(|M|+1)+2(s-|M|-1)=3d(y)+2(|A1|-1)≥3δ+|A1|-1=3δ+max{σ1,σ2}-1≥3δ.Case  2 (p¯≥2). We first prove that |C|≥2p¯+8. Since |NC(x)|≥2 and |NC(y)|≥2, there are at least two segments among I1,I2,…,Is of length at least p¯+2. If |M|=0, then clearly s≥4 and
(3.8)|C|≥2(p¯+2)+2(s-2)≥2p¯+8.
Otherwise, since max{|A1|,|A2|}≥1, there are at least three elementary segments of length at least p¯+2, that is,
(3.9)|C|≥3(p¯+2)≥2p¯+8.
So, in any case, |C|≥2p¯+8.
To prove that|C|≥4δ-2p¯, we distinguish two main cases.
Case  2.1 (|Ai|≥1(i=1,2)). It follows that among I1,I2,…,Is there are |M|+2 segments of length at least p¯+2. Further, since each of the remaining s-(|M|+2) segments has a length at least 2, we get
(3.10)|C|≥(p¯+2)(|M|+2)+2(s-|M|-2)=(p¯-2)|M|+(2p¯+4|M|+4)+2(|A1|+|A2|-2)≥2|A1|+2|A2|+4|M|+2p¯.
Observing also that
(3.11)|A1|+|M|+p¯≥d(x),|A2|+|M|+p¯≥d(y),
we have
(3.12)2|A1|+2|A2|+4|M|+2p¯≥2d(x)+2d(y)-2p¯≥4δ-2p¯,
implying that |C|≥4δ-2p¯.
Case  2.2 (either |A1|≥1, |A2|=0 or |A1|=0, |A2|≥1). Assume without loss of generality that |A1|≥1 and |A2|=0, that is, |NC(y)|=|M|≥2 and s=|A1|+|M|. It follows that among I1,I2,…,Is there are |M|+1 segments of length at least p¯+2. Observing also that |M|+p¯≥d(y)≥δ, that is, 2p¯+4|M|≥4δ-2p¯, we get
(3.13)|C|≥(p¯+2)(|M|+1)≥(p¯-2)(|M|-1)+2p¯+4|M|≥2p¯+4|M|≥4δ-2p¯.Proof of Lemma2.2.
Letξ1,ξ2,…,ξs be the elements of NC(x) occuring on C in a consecutive order. Put Ii=ξiC→ξi+1(i=1,2,…,s), where ξs+1=ξ1. To prove (a1), let L=zL→w be an intermediate path between elementary segments Ia and Ib with z∈V(Ia*) and w∈V(Ib*). Put
(3.14)|ξaC→z|=d1,|zC→ξa+1|=d2,|ξbC→w|=d3,|wC→ξb+1|=d4,C′=ξaxP→yξbC←zL→wC→ξa.
Clearly,
(3.15)|C′|=|C|-d1-d3+|L|+|P|+2.
Since C is extreme, we have |C|≥|C′|, implying that d1+d3≥p¯+|L|+2. By a symmetric argument, d2+d4≥p¯+|L|+2. Hence
(3.16)|Ia|+|Ib|=∑i=14‍di≥2p¯+2|L|+4.
The proof of(a1) is complete. To prove (a2), let Υ(Ia,Ib)⊆E(G) and |Υ(Ia,Ib)|=i for some i∈{1,2,3}.
Case  1 (i=1). It follows that Υ(Ia,Ib) consists of a unique intermediate edge L=zw. By (a1),
(3.17)|Ia|+|Ib|≥2p¯+2|L|+4=2p¯+6.Case 2 (i=2). It follows that Υ(Ia,Ib) consists of two edges e1, e2. Put e1=z1w1 and e2=z2w2, where {z1,z2}⊆V(Ia*) and {w1,w2}⊆V(Ib*).
Case  2.1 (z1≠z2 and w1≠w2). Assume without loss of generality that z1 and z2 occur in this order on Ia.
Case  2.1.1.w2 and w1 occur in this order on Ib.
Put(3.18)|ξaC→z1|=d1,|z1C→z2|=d2,|z2C→ξa+1|=d3,|ξbC→w2|=d4,|w2C→w1|=d5,|w1C→ξb+1|=d6,C′=ξaC→z1w1C←w2z2C→ξbxP→yξb+1C→ξa.
Clearly,
(3.19)|C′|=|C|-d2-d4-d6+|{e1}|+|{e2}|+|P|+2=|C|-d2-d4-d6+p¯+4.
Since C is extreme, |C|≥|C′|, implying that d2+d4+d6≥p¯+4. By a symmetric argument, d1+d3+d5≥p¯+4. Hence
(3.20)|Ia|+|Ib|=∑i=16‍di≥2p¯+8.Case  2.1.2. w1 and w2 occur in this order on Ib.
Putting(3.21)C′=ξaC→z1w1C→w2z2C→ξbxP→yξb+1C→ξa,
we can argue as in Case  2.1.1.
Case  2.2 (either z1=z2, w1≠w2 or z1≠z2, w1=w2). Assume without loss of generality that z1≠z2, w1=w2 and z1,z2 occur in this order on Ia. Put
(3.22)|ξaC→z1|=d1,|z1C→z2|=d2,|z2C→ξa+1|=d3,|ξbC→w1|=d4,|w1C→ξb+1|=d5,C′=ξaxP→yξbC←z1w1C→ξa,C′′=ξaC→z2w1C←ξa+1xP→yξb+1C→ξa.
Clearly,(3.23)|C′|=|C|-d1-d4+|{e1}|+|P|+2=|C|-d1-d4+p¯+3,|C′′|=|C|-d3-d5+|{e2}|+|P|+2=|C|-d3-d5+p¯+3.
Since C is extreme, |C|≥|C′| and |C|≥|C′′|, implying that
(3.24)d1+d4≥p¯+3,d3+d5≥p¯+3.
Hence,
(3.25)|Ia|+|Ib|=∑i=15‍di≥d1+d3+d4+d5+1≥2p¯+7.Case  3 (i=3). It follows that Υ(Ia,Ib) consists of three edges e1, e2, e3. Let ei=ziwi  (i=1,2,3), where {z1,z2,z3}⊆V(Ia*) and {w1,w2,w3}⊆V(Ib*). If there are two independent edges among e1, e2, e3, then we can argue as in Case  2.1. Otherwise, we can assume without loss of generality that w1=w2=w3 and z1, z2, z3 occur in this order on Ia. Put
(3.26)|ξaC→z1|=d1,|z1C→z2|=d2,|z2C→z3|=d3,|z3C→ξa+1|=d4,|ξbC→w1|=d5,|w1C→ξb+1|=d6,C′=ξaxP→yξbC←z1w1C→ξa,C′′=ξaC→z3w1C←ξa+1xP→yξb+1C→ξa.
Clearly,(3.27)|C′|=|C|-d1-d5+|{e1}|+p¯+2,|C′′|=|C|-d4-d6+|{e3}|+p¯+2.
Since C is extreme, we have |C|≥|C′| and |C|≥|C′′|, implying that
(3.28)d1+d5≥p¯+3,d4+d6≥p¯+3.
Hence,
(3.29)|Ia|+|Ib|=∑i=16‍di≥d1+d4+d5+d6+2≥2p¯+8.Proof of Lemma2.3.
Put(3.30)V(H)={v1,…,vh},|N(vi)∩S|=βi(i=1,…,h).
Observing thath≥d(vi)-βi+1≥δ-βi+1 for each i∈{1,2,…,h}, we have βi≥δ-h+1  (i=1,2,…,h). Therefore,
(3.31)qH=q(H)+∑i=1h‍βi=12∑i=1h‍dH(vi)+∑i=1h‍βi,=12∑i=1h‍(dH(vi)+βi)+12∑i=1h‍βi=12∑i=1h‍d(vi)+12∑i=1h‍(δ-h+1),≥12hδ+12h(δ-h+1)=h(2δ-h+1)2.Proof of Lemma2.4.
LetC be a longest cycle in G and P=x1P→x2 a longest path in G∖C of length p¯. If |V(P)|≤1, then C is a dominating cycle and we are done. Let |V(P)|≥2, that is, p¯≥1. By the hypothesis, |C|+p¯+1≤n≤3δ+2. Further, by Theorem D, |C|≥2δ. From these inequalities, we get(3.32)n≤3δ+2,|C|≤3δ-p¯+1,1≤p¯≤δ+1.
Letξ1,ξ2,…,ξs be the elements of NC(x1)∪NC(x2) occuring on C in a consecutive order. Put
(3.33)Ii=ξiC→ξi+1,Ii*=ξi+C→ξi+1-(i=1,2,…,s),
where ξs+1=ξ1.
Case  1 (δ=2). Let Q be a longest path in G with Q=ξQ→η and V(Q)∩V(C)={ξ,η}. Since C is extreme, we have |ξC→η|≥|Q| and |ηC→ξ|≥|Q|, implying that
(3.34)|C|=|ξC→η|+|ηC→ξ|≥2|Q|.
Since κ≥2 and p¯≥1, we have |Q|≥3. By (3.34), |C|≥2|Q|≥6, implying that q≥|C|+|Q|≥9.
Case  2. (δ≥3).
Case  2.1 (p¯=1). By (3.32),
(3.35)|C|≤3δ.Case  2.1.1 (NC(x1)≠NC(x2)). It follows that max{σ1,σ2}≥1, where
(3.36)σ1=|NC(x1)∖NC(x2)|,σ2=|NC(x2)∖NC(x1)|.
By Lemma 2.1, |C|≥3δ. Recalling (3.35), we get |C|=3δ. If max{σ1,σ2}≥2, then by Lemma 2.1, |C|≥3δ+1, contradicting (3.35). Let max{σ1,σ2}=1. Clearly, s≥δ and |Ii|≥3(i=1,2,…,s). Further, if s≥δ+1, then |C|≥3s≥3δ+3, again contradicting (3.35). Let s=δ, implying that |Ii|=3  (i=1,2,…,s). By Lemma 2.2, Υ(I1,I2,…,Is)=∅. Let H1,H2,…,Hs+1 be the connected components of G∖{ξ1,ξ2,…,ξs} with V(Hi)=V(Ii*)(i=1,2,…,s) and V(Hs+1)={x1,x2}. For each i∈{1,2,…,s+1}, put
(3.37)hi=|V(Hi)|,qi=|{xy∈E(G):{x,y}∩V(Hi)≠∅}|.
Clearly, hi=2(i=1,2,…,s+1). By Lemma 2.3,
(3.38)qi≥hi(2δ-hi+1)2=2δ-1(i=1,2,…,s+1),
implying that
(3.39)q≥∑i=1s+1‍qi≥(s+1)(2δ-1)=(δ+1)(2δ-1)>3(δ-1)(δ+2)2.Case  2.1.2 (NC(x1)=NC(x2)). Clearly, s≥δ-1. If s≥δ, then we can argue as in Case  2.1.1. Let s=δ-1. Further, if |Ii|+|Ij|≥10 for some distinct i,j∈{1,2,…,s}, then |C|≥10+3(s-2)=3δ+1, contradicting (3.35). Hence
(3.40)|Ii|+|Ij|≤9foreachdistincti,j∈{1,2,…,s}.Claim1. Υ(I1,I2,…,Is)⊆E(G) and(1)
ifmaxi|Ii|≤4 then |Υ(I1,I2,…,Is)|≤3,(2)
ifmaxi|Ii|=5 then |Υ(I1,I2,…,Is)|≤δ-1,(3)
ifmaxi|Ii|=6 then |Υ(I1,I2,…,Is)|≤2(δ-2).
Proof.If Υ(I1,I2,…,Is)=∅ then we are done. Otherwise, Υ(Ia,Ib)≠∅, for some distinct a,b∈{1,2,…,s}. By definition, there is an intermediate path L between Ia and Ib. If |L|≥2, then by Lemma 2.2,
(3.41)|Ia|+|Ib|≥2p¯+2|L|+4≥10,
contradicting (3.40). Otherwise, |L|=1 and therefore, Υ(I1,I2,…,Is)⊆E(G). By Lemma 2.2, |Ia|+|Ib|≥2p¯+6=8. Combining this with (3.40), we have
(3.42)8≤|Ia|+|Ib|≤9.
Furthermore, if |Υ(Ia,Ib)|≥3, then by Lemma 2.2, |Ia|+|Ib|≥2p¯+8=10, contradicting (3.42). So,
(3.43)1≤|Υ(Ii,Ij)|≤2foreachdistincti,j∈{1,2,…,s}.
Put r=|{i:|Ii|≥4}|. If r≥4, then |C|≥16+3(s-4)=3δ+1, contradicting (3.35). Further, if r=0, then by Lemma 2.2, Υ(I1,I2,…,Is)=∅. Let 1≤r≤3.
Case
a
1 (r=3). It follows that |Ii|≥4(i=a,b,c) for some distinct a,b,c∈{1,2,…,s} and |Ii|=3 for each i∈{1,2,…,s}∖{a,b,c}. Recalling that s=δ-1 and |C|=3δ, we have |Ia|=|Ib|=|Ic|=4, that is, maxi|Ii|=4. By Lemma 2.2, |Υ(Ii,Ij)|≤1 for each distinct i,j∈{a,b,c}. Moreover, we have |Υ(Ii,Ij)|=0 if either i∉{a,b,c} or j∉{a,b,c}. So,
(3.44)|Υ(I1,I2,…,Is)|=|Υ(Ia,Ib,Ic)|≤3.Casea2 (r=2). It follows that |Ia|≥4 and |Ib|≥4 for some distinct a,b∈{1,2,…,s} and |Ii|=3 for each i∈{1,2,…,s}∖{a,b}. By (3.42), we can assume without loss of generality that either |Ia|=|Ib|=4 or |Ia|=5, |Ib|=4.
Case
a
2.1 (|Ia|=|Ib|=4). It follows that maxi|Ii|=4. By Lemma 2.2, |Υ(Ia,Ib)|≤1 and Υ(Ii,Ij)=∅ if {i,j}≠{a,b}, implying that |Υ(I1,I2,…,Is)|=|Υ(Ia,Ib)|≤1.
Case
a
2.2 (|Ia|=5, |Ib|=4). It follows that maxi|Ii|=5. By Lemma 2.2, we have |Υ(Ia,Ib)|≤2 and |Υ(Ia,Ii)|≤1 for each i∈{1,2,…,s}∖{a,b}. Furthermore, Υ(Ii,Ij)=∅ if a∉{i,j}. Thus, |Υ(I1,I2,…,Is)|≤δ-1.
Case
a
3 (r=1). It follows that |Ia|≥4 for some a∈{1,2,…,s} and |Ii|=3 for each i∈{1,2,…,s}∖{a}. By (3.42), 4≤|Ia|≤6.
Case
a
3.1 (|Ia|=4). It follows that maxi|Ii|=4. By Lemma 2.2, Υ(Ia,Ii)=∅ for each i∈{1,2,…,s}∖{a}, implying that |Υ(I1,I2,…,Is)|=0.
Case
a
3.2 (|Ia|=5). It follows that maxi|Ii|=5. By Lemma 2.2, |Υ(Ia,Ii)|≤1 for each i∈{1,2,…,s}∖{a} and Υ(Ii,Ij)=∅ if a∉{i,j}, that is, |Υ(I1,I2,…,Is)|≤δ-2.
Case
a
3.3 (|Ia|=6). It follows that maxi|Ii|=6. By Lemma 2.2, |Υ(Ia,Ii)|≤2 for each i∈{1,2,…,s}∖{a} and Υ(Ii,Ij)=∅ if a∉{i,j}, that is, |Υ(I1,I2,…,Is)|≤2(δ-2). Claim 1 is proved.
Lete∈Υ(I1,I2,…,Is) and let e=zw, where z∈V(Ia*) and w∈V(Ib*) for some distinct a,b∈{1,2,…,s}. Put G′=G∖e. Form a graph G′′ in the following way. If d(z)≥δ and d(w)≥δ in G′ then we take G′′=G′. Next, suppose that d(z)=δ-1 and d(w)≥δ in G′. Put(3.45)U1=({ξ1,ξ2,…,ξs}∪V(Ia*))∖{z},U2=({ξ1,ξ2,…,ξs}∪V(Ib*))∖{w}.
If U1⊆N(z), then clearly d(z)≥|U1|=δ in G′, contradicting the hypothesis. Otherwise, zv∉E(G′) for some v∈U1 and we take G′′=G′+{zv}. Finally, if d(z)=d(w)=δ-1, then as above, zv∉E(G′) and wu∉E(G′) for some v∈U1, u∈U2 and we take G′′=G′+{zv,wu}. Clearly, δ(G′′)=δ(G) and q=q(G)≥q(G′′)-1. This procedure may be repeated for all edges of Υ(I1,I2,…,Is). The resulting graph G* satisfies the following conditions:
(3.46)δ(G*)=δ(G),q(G)≥q(G*)-|Υ(I1,I2,…,Is)|.
In fact,
(3.47)G*=(G∖Υ(I1,I2,…,Is))+E*,
where E* consists of at most 2|Υ(I1,I2,…,Is)| appropriate new edges such that G*∖{ξ1,ξ2,…,ξs} is disconnected. Let H1,H2,…,Ht be the connected components of G*∖{ξ1,ξ2,…,ξs} with V(Ii*)⊆V(Hi)  (i=1,2,…,s) and V(Hs+1)={x1,x2}. For each i∈{1,2,…,s+1}, put
(3.48)hi=|V(Hi)|,qi=|{xy∈E(G*):{x,y}∩V(Hi)≠∅}|.
Clearly, hi≥2(i=1,2,…,s+1). If hi≥6 for some i∈{1,2,…,s}, then
(3.49)n≥∑i=1s+1‍hi+|{ξ1,ξ2,…,ξs}|≥6+3s=3δ+3,
contradicting (3.32). Otherwise, 2≤hi≤5≤2δ-1(i=1,2,…,s+1). It follows that (hi-2) (2δ-hi-1)≥0 which is equivalent to
(3.50)hi(2δ-hi+1)2≥2δ-1(i=1,2,…,s+1).Case  2.1.2.1 (maxi|Ii|≤4). By (3.50) and Lemma 2.3, qi(G*)≥2δ-1(i=1,2,…,s+1). Hence
(3.51)q(G*)≥∑i=1s+1‍qi(G*)≥(s+1)(2δ-1)=δ(2δ-1).
Using (3.46) and Claim 1, we have
(3.52)q≥q(G*)-3≥δ(2δ-1)-3≥3(δ-1)(δ+2)2.Case  2.1.2.2 (maxi|Ii|=5). Assume without loss of generality that maxi|Ii|=|I1|=5, that is, 4≤h1≤5. By (3.50) and Lemma 2.3, qi(G*)≥2δ-1(i=2,…,s+1) and
(3.53)q1(G*)≥h1(2δ-h1+1)2≥2(2δ-3).
Hence
(3.54)q(G*)≥s(2δ-1)+2(2δ-3)=2δ2+δ-5.
By (3.46) and Claim 1,
(3.55)q≥q(G*)-(δ-1)≥2δ2-4>3(δ-1)(δ+2)2.Case  2.1.2.3 (maxi|Ii|=6). Assume without loss of generality that maxi|Ii|=|I1|=6, that is, h1=5. By (3.50) and Lemma 2.3, qi(G*)≥2δ-1(i=2,…,s+1) and
(3.56)q1(G*)≥h1(2δ-h1+1)2=5(δ-2).
Hence
(3.57)q(G*)≥s(2δ-1)+5(δ-2)=2δ2+2δ-9.
By (3.46) and Claim 1,
(3.58)q≥q(G*)-2(δ-2)≥2δ2-5>3(δ-1)(δ+2)2.Case  2.2 (p¯≥2). According to (3.32), we can distinguish five main cases, namely, 2≤p¯≤δ-3, p¯=δ-2, p¯=δ-1, p¯=δ, and p¯=δ+1.
Case  2.2.1 (2≤p¯≤δ-3). It follows that |NC(xi)|≥δ-p¯≥3(i=1,2) and
(3.59)δ≥5,δ-p¯≥3.
If NC(x1)≠NC(x2), then by (3.59) and Lemma 2.1, |C|≥4δ-2p¯≥3δ-p¯+3, contradicting (3.32). Let NC(x1)=NC(x2). Clearly, s≥|NC(x1)|-(|V(P)|-1)≥δ-p¯ and |Ii|≥p¯+2(i=1,2,…,s). If s≥δ-p¯+1, then
(3.60)|C|≥s(p¯+2)≥(δ-p¯+1)(p¯+2),=(δ-p¯-1)(p¯-1)+3δ-p¯+1≥3δ-p¯+3,
again contradicting (3.32). Let s=δ-p¯. It means that x1x2∈E(G), that is, G[V(P)] is hamiltonian. By symmetric arguments, NC(y)=NC(x1) for each y∈V(P). Assume that Υ(I1,I2,…,Is)≠∅, that is, Υ(Ia,Ib)≠∅ for some elementary segments Ia and Ib. By the definition, there is an intermediate path L between Ia and Ib. If |L|≥2, then by Lemma 2.2(3.61)|Ia|+|Ib|≥2p¯+2|L|+4≥2p¯+8.
Hence
(3.62)|C|=|Ia|+|Ib|+∑i∈{1,…,s}∖{a,b}‍|Ii|≥2p¯+8+(s-2)(p¯+2),=(δ-p¯-2)(p¯-1)+3δ-p¯+2≥3δ-p¯+3,
contradicting (3.32). Thus, |L|=1, that is, Υ(I1,I2,…,Is)⊆E(G). By Lemma 2.2,
(3.63)|Ia|+|Ib|≥2p¯+2|L|+4=2p¯+6,
which yields
(3.64)|C|=|Ia|+|Ib|+∑i∈{1,…,s}∖{a,b}‍|Ii|≥2p¯+6+(s-2)(p¯+2)=(s-2)(p¯-2)+4δ-2p¯-2≥3δ-p¯-2+(δ-p¯).
If δ-p¯≥4, then |C|≥3δ-p¯+2, contradicting (3.32). Let δ-p¯≤3. Recalling (3.59), we have δ-p¯=3, that is, p¯=δ-3 and s=δ-p¯=3. Hence, |C|≥s(p¯+2)=3(δ-1). On the other hand, by (3.32) and the fact that p¯≥2, we have |C|≤3δ-p¯+1≤3δ-1. Thus
(3.65)3δ-3≤|C|≤3δ-1.
Put G′=G∖Υ(I1,I2,I3). As in Case  2.1.2, form a graph G* by adding at most 2|Υ(I1,I2,I3)| new edges in G′ such that δ(G*)=δ(G) and G*∖{ξ1,ξ2,ξ3} are disconnected. We denote G*=G immediately if Υ(I1,I2,I3)=∅. Hence
(3.66)q(G)≥q(G*)-|Υ(I1,I2,I3)|.
Let H1,H2,…,Ht be the connected components of G*∖{ξ1,ξ2,ξ3} with V(Ii*)⊆V(Hi)(i=1,2,3) and V(P)⊆V(H4). Since x1x2∈E(G)  (i.e., G[V(P)] is hamiltonian) and P is extreme, we have V(H4)=V(P). Using notation (3.48) for G*, we have hi≥|Ii|-1≥p¯+1=δ-2  (i=1,2,3) and h4=δ-2. If hi≥δ+1 for some i∈{1,2,3}, then
(3.67)n≥h1+h2+h3+h4+s≥4δ-2.
By (3.59), δ≥5, implying that 4δ-2≥3δ+3 and n≥3δ+3, contradicting (3.32). Let δ-2≤hi≤δ  (i=1,2,3,4). It follows that
(3.68)hi(2δ-hi+1)2≥(δ-2)(δ+3)2(i=1,2,3,4).
By Lemma 2.3, qi(G*)≥(δ-2)(δ+3)/2(i=1,2,3,4), implying that
(3.69)q(G*)≥∑i=14‍qi(G*)≥2(δ-1)(δ+3).
If |Υ(I1,I2,I3)|≥4, then |Υ(Ia,Ib)|≥2 for some distinct a,b∈{1,2,3}. By Lemma 2.2(3.70)|Ia|+|Ib|≥2p¯+7=2δ+1
and hence |C|≥3δ, contradicting (3.65). So, |Υ(I1,I2,I3)|≤3. By (3.66) and (3.69),
(3.71)q≥q(G*)-3≥2(δ-1)(δ+3)-3≥3(δ-1)(δ+2)2.Case  2.2.2 (p¯=δ-2). It follows that |NC(xi)|≥δ-p¯=2(i=1,2). By (3.32),
(3.72)|C|≤3δ+1-p¯=2δ+3.
If NC(x1)≠NC(x2), then by Lemma 2.1, |C|≥4δ-2p¯=2δ+4, contradicting (3.72). Let NC(x1)=NC(x2). Further, if s≥3, then
(3.73)|C|≥s(p¯+2)≥3δ=2δ+(p¯+2)≥2δ+4,
again contradicting (3.72). Let s=2. It follows that x1x2∈E(G), that is, G[V(P)] is hamiltonian. By symmetric arguments, NC(y)=NC(x1)={ξ1,ξ2} for each y∈V(P). Clearly, |Ii|≥p¯+2=δ(i=1,2).
Case  2.2.2.1 (Υ(I1,I2)=∅). It follows that G∖{ξ1,ξ2} is disconnected. Let H1,H2,…,Ht be the connected components of G∖{ξ1,ξ2} with V(Ii*)⊆V(Hi)(i=1,2) and V(P)⊆V(H3). Since P is extreme and G[V(P)] is hamiltonian, we have V(H3)=V(P). By notation (3.48), hi≥|Ii|-1≥δ-1(i=1,2) and h3=δ-1. If hi≥δ+3 for some i∈{1,2}, then
(3.74)n≥h1+h2+h3+|{ξ1,ξ2}|≥3δ+3,
contradicting (3.32). So, δ-1≤hi≤δ+2(i=1,2,3). By Lemma 2.3,
(3.75)qi≥hi(2δ-hi+1)2≥(δ-1)(δ+2)2(i=1,2,3).
Hence,
(3.76)q≥∑i=13‍qi≥3(δ-1)(δ+2)2.Case  2.2.2.2 (Υ(I1,I2)≠∅). By definition, there is an intermediate path L between I1 and I2. If |L|≥2, then by Lemma 2.2(3.77)|C|=|I1|+|I2|≥2p¯+2|L|+4≥2δ+4,
contradicting (3.72). Otherwise, Υ(I1,I2)⊆E(G). Further, if |Υ(I1,I2)|≥3, then by Lemma 2.2(3.78)|C|=|I1|+|I2|≥2p¯+8=2δ+4,
again contradicting (3.72). Thus |Υ(I1,I2)|≤2.
Case  2.2.2.2.1 (|Υ(I1,I2)|=1). Put G′=G∖Υ(I1,I2). As in Case  2.1.2, form a graph G* by adding at most two new edges in G′ such that δ(G*)=δ(G), G*∖{ξ1,ξ2} is disconnected and q(G)≥q(G*)-1. Let H1,H2,…,Ht be the connected components of G*∖{ξ1,ξ2} with V(Ii*)⊆V(Hi)(i=1,2) and V(P)=V(H3). Using notation (3.48) for G*, as in Case  2.2.2.1, we have δ-1≤hi≤δ+2(i=1,2,3). By Lemma 2.2, |I1|+|I2|≥2p¯+6=2δ+2. It means that maxi|Ii|≥δ+1, that is, maxihi≥δ. Assume without loss of generality that h1≥δ. By Lemma 2.3,
(3.79)q1(G*)≥h1(2δ-h1+1)2≥δ(δ+1)2,qi(G*)≥hi(2δ-hi+1)2≥(δ-1)(δ+2)2(i=2,3),
implying that
(3.80)q(G*)≥δ(δ+1)2+(δ-1)(δ+2).
Hence
(3.81)q≥q(G*)-1≥δ(δ+1)2+(δ-1)(δ+2)-1≥3(δ-1)(δ+2)2.Case  2.2.2.2.2 (|Υ(I1,I2)|=2). By Lemma 2.2,
(3.82)|C|=|I1|+|I2|≥2p¯+7=2δ+3.
Recalling (3.72), we get |C|=2δ+3 and V(G)=V(P∪C). Put G′=G∖Υ(I1,I2). As in Case  2.1.2, form a graph G* by adding at most four new edges in G′ such that δ(G*)=δ(G), G*∖{ξ1,ξ2} is disconnected and q(G)≥q(G*)-2. Let H1,H2, and H3 be the connected components of G*∖{ξ1,ξ2} with V(Hi)=V(Ii*)(i=1,2) and V(H3)=V(P). Using notation (3.48) for G*, we have as in Case  2.2.2.1, δ-1≤hi≤δ+2(i=1,2,3). Since |Ii|≥δ(i=1,2) and |C|=|I1|+|I2|=2δ+3, we can assume without loss of generality that either |I1|=δ+2, |I2|=δ+1 or |I1|=δ+3,  |I2|=δ.
Case  2.2.2.2.2.1 (|I1|=δ+2, |I2|=δ+1). It follows that h1=δ+1, h2=δ and h3=δ-1. By Lemma 2.3,
(3.83)qi(G*)≥hi(2δ-hi+1)2=δ(δ+1)2(i=1,2),q3(G*)≥h3(2δ-h3+1)2=(δ-1)(δ+2)2.
Hence
(3.84)q≥∑i=13‍qi(G*)-2≥δ(δ+1)-2+(δ-1)(δ+2)2=3(δ-1)(δ+2)2.
Case  2.2.2.2.2.2 (|I1|=δ+3, |I2|=δ). Let Υ(I1,I2)={e1,e2}, where
(3.85)e1=y1z1,e2=y2z2,{y1,y2}⊆V(I1*),{z1,z2}⊆V(I2*).
If y1≠y2 and z1≠z2, then as in proof of Lemma 2.2 (Case  2.1),
(3.86)|C|=|I1|+|I2|≥2p¯+8=2(δ-2)+8=2δ+4,
contradicting (3.72). Let either y1≠y2 and z1=z2 or y1=y2 and z1≠z2.
Case  2.2.2.2.2.2.1  (y1≠y2 and z1=z2). Assume without loss of generality that y1,y2 occur on I1 in this order. If y2=y1+, then
(3.87)|C|≥|ξ1C→y1z1y2C→ξ2x2P←x1ξ1|=2δ+4,
contradicting (3.72). Let y2≠y1+, that is, |y1C→y2|≥2. Put
(3.88)C′=ξ1C→y2z1C←ξ2x2P←x1ξ1,C′′=ξ1C←z1y1C→ξ2x2P←x1ξ1.
Clearly,
(3.89)|C|≥|C′|=|ξ1C→y1|+|y1C→y2|+|{e2}|+|ξ2C→z1|+(p¯+2),|C|≥|C′′|=|ξ1C←z1|+|{e1}|+|y1C→y2|+|y2C→ξ2|+(p¯+2).
By summing and observing that
(3.90)|ξ1C→y1|+|y1C→y2|+|y2C→ξ2|+|ξ2C→z1|+|z1C→ξ1|=|C|,
we get
(3.91)2|C|≥|C|+|y1C→y2|+2(p¯+2)+2≥|C|+2δ+4.
Hence |C|≥2δ+4, again contradicting (3.72).
Case  2.2.2.2.2.2.2 (y1=y2 and z1≠z2). Assume without loss of generality that z2,z1 occur on I2 in this order.
Case  2.2.2.2.2.2.2.1 (δ≥6). If |ξ1C→y1|≥δ-1 and |y1C→ξ2|≥δ-1, then |I1|≥2δ-2≥δ+4, contradicting the hypothesis. Thus, we can assume without loss of generality that |ξ1C→y1|≤δ-2. If y1-=ξ1, then
(3.92)|C|≥|ξ1C←z2y1C→ξ2x2P←x1ξ1|≥2δ+5,
contradicting (3.72). Let y1-≠ξ1, that is, y1-∈V(I1*). Since Υ(I1,I2)={y1z1,y1z2}, we have N(y1-)⊂V(I1). If N(y1-)∩V(y1+C→ξ2-)=∅, then |N(y1-)|≤δ-1, a contradiction. Otherwise, y1-w∈E(G) for some w∈V(y1+C→ξ2-). Put
(3.93)R=ξ1C→y1-wC←y1,C′=ξ1R→y1z1C←ξ2x2P←x1ξ1,C′′=ξ1C←z2y1C→ξ2x2P←x1ξ1.
Clearly,
(3.94)|C|≥|C′|=|R|+|{y1z1}|+|z1C←ξ2|+(p¯+2),|C|≥|C′′|=|ξ1C←z1|+|z1C←z2|+|{y1z2}|+|y1C→ξ2|+(p¯+2).
By summing and observing that |R|≥|ξ1C→y1|+1, we get
(3.95)2|C|≥(|ξ1C→y1|+|y1C→ξ2|+|ξ2C→z1|+|z1C→ξ1|)+2(p¯+2)+4=|C|+2δ+4.
Hence |C|≥2δ+4, contradicting (3.72).
Case  2.2.2.2.2.2.2.2 (δ=5). It follows that
(3.96)|I1|=δ+3=8,|I2|=δ=5,|C|=2δ+3=13.
If either |ξ1C→y1|≤δ-2=3 or |y1C→ξ2|≤δ-2=3, then we can argue as in Case  2.2.2.2.2.2.2.1. Otherwise, |ξ1C→y1|=|y1C→ξ2|=4. If |z1C←ξ2|≥4, then
(3.97)|ξ1C→y1z1C←ξ2x2P←x1ξ1|≥14>|C|,
a contradiction. Let |z1C←ξ2|≤3. Similarly, |ξ1C←z2|≤3, implying that I2=ξ2ξ2+z2z1z1+ξ1. If z1+z2∈E(G), then
(3.98)|ξ1C→y1z1z1+z2C←ξ2x2P←x1ξ1|=14>|C|,
a contradiction. So, N(z1+)⊆{ξ1,ξ2,z1,ξ2+}, again a contradiction, since |N(z1+)|≥δ=5.
Case  2.2.2.2.2.2.2.3 (δ=4). It follows that
(3.99)|I1|=δ+3=7,|I2|=δ=4,|C|=2δ+3=11.
Since |I1|=7, we have either |ξ1C→y1|≥4 or |y1C→ξ2|≥4, say |ξ1C→y1|≥4. Put
(3.100)C′=ξ1C→y1z1C←ξ2x2P←x1ξ1.
If |ξ1C→y1|≥5, then |C′|≥12>|C|, a contradiction. This means that |ξ1C→y1|=4. If |z1C→ξ1|=1 then |C′|≥12>|C|, a contradiction. Let |z1C→ξ1|≥2. Since |I2|=4, we have |z1C→ξ1|=2, that is, I2=ξ2z2z1z1+ξ1. Further, if z1+z2∈E(G), then
(3.101)|ξ1C→y1z1z1+z2ξ2x2P←x1ξ1|=12>|C|,
a contradiction. Let z1+z2∉E(G). Since |Υ(I1,I2)|=2, we have N(z1+)⊆{ξ1,ξ2,z1}, contradicting the fact that |N(z1+)|≥δ=4.
Case  2.2.3 (p¯=δ-1). By (3.32),
(3.102)|C|≤3δ+1-p¯=2δ+2.
It follows that |NC(xi)|≥δ-p¯=1(i=1,2).
Case  2.2.3.1 (|NC(xi)|≥2(i=1,2)). If NC(x1)≠NC(x2), then by Lemma 2.1, |C|≥2p¯+8=2δ+6, contradicting (3.102). Let NC(x1)=NC(x2). If s≥3, then
(3.103)|C|≥s(p¯+2)≥3(δ+1)>2δ+2,
contradicting (3.102). Let s=2. It follows that |C|≥s(p¯+2)≥2(δ+1). Recalling (3.102), we get
(3.104)|C|=2δ+2,|I1|=|I2|=δ+1,V(G)=V(C∪P).
Assume that yz∈E(G) for some y∈V(P) and z∈V(C)∖{ξ1,ξ2}. Besides, we can assume without loss of generality that z∈V(I1*). Since C is extreme, we have
(3.105)|ξ1C→z|≥|x1P→y|+2,|zC→ξ2|≥|yP→x2|+2,
implying that
(3.106)|I1|=|ξ1C→z|+|zC→ξ2|≥|x1P→y|+|yP→x2|+4=p¯+4=δ+3,
a contradiction. So, NC(y)⊆{ξ1,ξ2} for each y∈V(P). On the other hand, by Lemma 2.2, Υ(I1,I2)=∅ and hence G∖{ξ1,ξ2} is disconnected. Let H1,H2, and H3 be the connected components of G∖{ξ1,ξ2} with V(Hi)=V(Ii*)(i=1,2) and V(H3)=V(P). Using notation (3.48), we have hi=δ(i=1,2,3). By Lemma 2.3,
(3.107)qi≥hi(2δ-hi+1)2=δ(δ+1)2(i=1,2,3),
implying that
(3.108)q≥∑i=13‍qi≥3(δ2+δ)2>3(δ-1)(δ+2)2.Case  2.2.3.2 (either |NC(x1)|=1 or |NC(x2)|=1). Assume without loss of generality that |NC(x1)|=1. Put NC(x1)={y1}.
Case  2.2.3.2.1 (NC(x2)≠NC(x1)). It follows that x2y2∈E(G) for some y2∈V(C)∖{y1} and we can argue as in Case  2.2.3.1.
Case  2.2.3.2.2 (NC(x2)=NC(x1)={y1}). It follows that
(3.109)N(xi)=(V(P)∖{xi})∪{y1}(i=1,2).
Since κ≥2, there is an edge zw such that z∈V(P) and w∈V(C)∖{y1}. Since NC(x1)=NC(x2)={y1}, we have z∉{x1,x2}. By (3.109), x2z-∈E(G). Then replacing P with x1P→z-x2P←z, we can argue as in Case  2.2.3.1.
Case  2.2.4 (p¯=δ). By (3.32), |C|≤3δ+1-p¯=2δ+1. Let Q=ξQ→η be a longest path in G with V(Q)∩V(C)={ξ,η}. If |Q|≥δ+1, then by (3.34), |C|≥2|Q|≥2δ+2, a contradiction. Let
(3.110)|Q|≤δ.Case  2.2.4.1 (x1x2∉E(G)). It follows that |NC(xi)|≥1  (i=1,2). If |NC(xi)|≥2 for some i∈{1,2}, then clearly |Q|≥p¯+2=δ+2, contradicting (3.110). Let |NC(x1)|=|NC(x2)|=1. Further, if NC(x1)≠NC(x2), then again |Q|≥δ+2, contradicting (3.110). Let NC(x1)=NC(x2)={z1} for some z1∈V(C). Since κ≥2, there is a path L=yz2 connecting P and C such that y∈V(P) and z2∈V(C)∖{z1}. Clearly, y∉{x1,x2}. If x2y-∈E(G), then
(3.111)|Q|≥|z1x1P→y-x2P←yz2|=δ+2,
contradicting (3.110). Let x2y-∉E(G). Further, if y-≠x1, then recalling that x2x1∉E(G) we have |NC(x2)|≥2, a contradiction. Otherwise, y-=x1 and |Q|≥|z1x2P←yz2|=δ+1, contradicting (3.110).
Case  2.2.4.2  (x1x2∈E(G)). Put C′=x1P→x2x1. Since κ≥2, there are two disjoint paths L1,L2 connecting C′ and C. Further, since P is extreme, we have |L1|=|L2|=1. Let L1=y1z1 and L2=y2z2, where y1,y2∈V(C′) and z1,z2∈V(C). Since C′ is a hamiltonian cycle in G[V(P)], we can assume that P is chosen such that x1=y1. If |x1P→y2|≤2, then |Q|≥|z1x1x2P←y2z2|≥δ+1, contradicting (3.110). Let |x1P→y2|≥3. If x2v∈E(G) for some v∈{y2-1,y2-2}, then
(3.112)|Q|≥|z1x1P→vx2P←y2z2|≥δ+1,
contradicting (3.110). Otherwise, |NC(x2)|≥2, implying that x2z3∈E(G) for some z3∈V(C)∖{z1}. Then
(3.113)|Q|≥|z1x1P→x2z3|≥δ+2,
again contradicting (3.110).
Case  2.2.5 (p¯=δ+1). By (3.32), |C|≤3δ+1-p¯=2δ. On the other hand, by Theorem D, |C|≥2δ, implying that |C|=2δ and V(G)=V(C∪P). Let Q=ξQ→η be a longest path in G with V(Q)∩V(C)={ξ,η}. If |Q|≥δ+1, then by (3.35), |C|≥2|Q|≥2δ+2, a contradiction. Let
(3.114)|Q|≤δ.Case  2.2.5.1 (x1x2∈E(G)). Put C′=x1P→x2x1. Since κ≥2, there are two disjoint edges z1w1 and z2w2 connecting C′ and C such that z1,z2∈V(C′) and w1,w2∈V(C). Since C′ is a hamiltonian cycle in G[V(P)], we can assume without loss of generality that P is chosen such that z1=x1. If |x1P→z2|≤3, then |Q|≥|w1x1x2P←z2w2|≥δ+1, contradicting (3.114). Let |x1P→z2|≥4. Further, if x2v∈E(G) for some v∈{z2-1,z2-2,z2-3}, then
(3.115)|Q|≥|w1x1P→vx2P←z2w2|≥δ+1,
contradicting (3.114). Now let x2v∉E(G) for each v∈{z2-1,z2-2,z2-3}. It follows that |NC(x2)|≥2, that is, x2w3∈E(G) for some w3∈V(C)∖{w1}. But then |Q|≥|w1x1P→x2w3|=δ+3, contradicting (3.114).
Case  2.2.5.2 (x1x2∉E(G)). If dP(x1)+dP(x2)≥|V(P)|=p¯+1=δ+2 then by Theorem C, G[V(P)] is hamiltonian and we can argue as in Case  2.2.5.1. Otherwise, dP(x1)+dP(x2)≤δ+1, implying that
(3.116)dC(x1)+dC(x2)≥δ-1≥2.
Assume without loss of generality that dC(x1)≥dC(x2).
Case  2.2.5.2.1 (dC(x2)=0). It follows that N(x2)=V(P)∖{x1,x2}. By (3.116), dC(x1)≥2. Put C′=x1+P→x2x1+. Since κ≥2, there is a path L=zL→w connecting C′ and C such that z∈V(C′)∖{x1+} and w∈V(C). If x1∈V(L), that is, x1z∈E(G), then x1P→z-x2P←zx1 is a hamiltonian cycle in G[V(P)] and we can argue as in Case  2.2.5.1. Let x1∉V(L). Since V(G)=V(C∪P), we have L=zw. Further, since dC(x1)≥2, we have x1w1∈E(G) for some w1∈V(C)∖{w}. Hence,
(3.117)|Q|≥|w1x1P→z-x2P←zw|=δ+3,
contradicting (3.114).
Case  2.2.5.2.2 (dC(x2)=1). Let NC(x2)={w1}. By (3.116), dC(x1)≥1. If either dC(x1)≥2 or NC(x1)≠NC(x2), then x1w∈E(G) for some w∈V(C)∖{w1} and therefore
(3.118)|Q|≥|wx1P→x2w1|=δ+3,
contradicting (3.114). Otherwise, NC(x1)=NC(x2)={w1}. Since κ≥2, there is an edge zw such that z∈V(P) and w∈V(C)∖{w1}. Clearly, z∉{x1,x2}. Further, we can argue as in Case  2.2.5.1.
Case  2.2.5.2.3 (dC(x2)≥2). Since dC(x1)≥dC(x2), we have dC(x1)≥2. Hence |Q|≥p¯+2=δ+3, contradicting (3.114).Proof of Theorem1.1.
LetG be a graph satisfying the hypothesis of Theorem 1.1, which is equivalent to
(3.119)q≤δ2+δ-1.
Since
(3.120)q=12∑u∈V(G)‍d(u)≥δn2,
we have δn/2≤δ2+δ-1 which is equivalent to
(3.121)δ≥n-12-12+1δ.
If n is even, that is, n=2t for some integer t, then
(3.122)δ≥2t-12-12+1δ=t-1+1δ,
implying that δ≥t=n/2. By Theorem A, G is hamiltonian. Let n is odd, that is, n=2t+1 for some integer t. Then δ≥t-1/2+1/δ implying that δ≥t≥(n-1)/2. Recalling that G is hamiltonian when δ>(n-1)/2, we can assume that δ=(n-1)/2. By Theorem C, either G is hamiltonian or containers at least δ2+δ edges, contradicting (3.119). Theorem 1.1 is proved.Proof of Theorem1.2.
LetG be a 2-connected graph. The hypothesis of Theorem 1.2 is equivalent to
(3.123)q≤{8whenδ=2,3(δ-1)(δ+2)-12whenδ≥3.Case  1 (δ=2 and q≤8). Let C be a longest cycle in G and P=x1P→x2 a longest path in G∖C of length p¯. If p¯=0, then C is a dominating cycle and we are done. Let p¯≥1. Since κ≥2, there is a path Q=ξQ→η such that V(Q)∩V(C)={ξ,η} and |Q|≥3. Further, since C is extreme, we have |C|=|ξC→η|+|ηC→ξ|≥2|Q|≥6 and therefore, q≥|C|+|Q|≥9, contradicting the hypothesis.
Case  2 (δ≥3 and q≤(3(δ-1)(δ+2)-1)/2). Since
(3.124)q=12∑u∈V(G)‍d(u)≥δn2,
we have δn/2≤(3(δ-1)(δ+2)-1)/2, which is equivalent to
(3.125)δ≥n-23-13+73δ.
If n=3t for some integer t, then
(3.126)δ≥3t-23-13+73δ=t-1+73δ,
implying that δ≥t=n/3>(n-2)/3. Next, if n=3t+1 for some integer t, then
(3.127)δ≥3t-13-13+73δ=t-23+73δ,
implying that δ≥t=(n-1)/3>(n-2)/3. Finally, if n=3t+2 for some integer t, then
(3.128)δ≥3t3-13+73δ=t-13+73δ,
implying that δ≥t=(n-2)/3. So, δ≥(n-2)/3, in any case. By Lemma 2.4, each longest cycle in G is a dominating cycle.



---

*Source: 185346-2012-12-10.xml*