# Hamiltonicity of3tEC Graphs with α=κ+1

Authors: Huanying He; Xinhui An; Zongjun Zhao
Journal: Journal of Mathematics
 (2021)

---

## Abstract

A setS of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γtG of G. The graph G is total domination edge-critical, or γtEC, if for every edge e in the complement of G, γtG+e<γtG. If G is γtEC and γtG=k, we say that G is ktEC. In this paper, we show that every 3tEC graph with δG≥2 and αG=κG+1 has a Hamilton cycle.


---

## Body

## 1. Introduction

All graphs we considered here are finite, undirected, and simple. We refer to [1] for unexplained terminology and notations. Let G=VG,EG be a graph with vertex set VG and edge set EG. For a vertex v of G, the open neighborhood of v is the set Nv=u∈V:uv∈EG, and closed neighborhood of v is Nv=Nv∪v. For a set S⊆VG, its open neighborhood is the set NS=∪v∈SNv, and its closed neighborhood is the set NS=NS∪S. The complement G¯ of G has vertex set VG and edge set xy|x,y⊆VG,xy∉EG. The subgraph of G induced by the nonempty vertex subset S⊆VG will be denoted by GS, and set G−S=GVG−S. We use ωG−S to denote the number of components of G−S. An independent set of the graph G is a set of vertices, no two of which are adjacent. The independence number of G, denoted by αG, is the order of a maximum independent set in G. The connectivity of G, denoted by κG, is defined as the order of the minimum vertex subset whose deletion resulting in G is disconnected. We often simply write α for αG and κ for κG, respectively. A Hamilton path of G is a path passing exactly once through every vertex of G. A Hamilton cycle is a closed Hamilton path. We refer to [2–4] for some recent results on the Hamiltonian properties of graphs.The domination theory of graphs is an important part of graph theory because of its wide range of applications and theoretical significance [5, 6]. A subset S⊆VG is called a dominating set of a graph G if for every v∈VG, either v∈S or v is adjacent to a vertex in S. The domination number of G, denoted by γG, is the minimum cardinality of a dominating set. The graph G is said to be domination edge-critical, or γEC, if for every edge e∈EG¯, γG+e<γG. If G is γEC and γG=k, we say that G is kEC. A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γtG of G. We refer to [7–12] for some recent results on the domination number and total domination number of G. As introduced in [13], a graph G is total domination edge-critical, or γtEC, if for every edge e∈EG¯, γtG+e<γtG. If G is γtEC and γtG=k, we say that G is ktEC. We refer to [14–18] for some results on γtEC graphs.In [11], Pan et al. proved that the total edge domination problem is NP-complete for bipartite graphs with maximum degree 3. In [19], Furuya and Matsumoto showed that the order of a connected 3-edge-critical planar graph is at most 23.For the sake of convenience, we writeu⇒v (or v⇒u if uv∈EG. In general, for subsets S and T of VG, if every vertex in T has a neighbor in S, we say that S dominates T and write S⇒T.The study of total domination edge-critical graphs was initiated in [13]. It was shown in [13] that the addition of an edge to a graph can change the total domination number by at most two. If G is γtEC graph, γtG−2≤γtG+e≤γtG for any edge e∈EG¯. Since γtG≥2 for any graph G, if G is 3tEC, then γtG+e=2 for any edge e∈EG¯. Also, observe that any graph G with γtG=3 is connected. In [14], Asplund et al. constructed some families of γtEC graphs with diameter 2 and determined which γtEC graphs have complements that are 3tEC graphs.We also use the following results on3tEC graphs.Theorem 1 (see [13]).
For any3tEC graph G and nonadjacent vertices u and v, at least one of the following holds:(1)
u,v dominates G(2)
There existsw∈Nu such that u,w dominates G−v, but not v, and we write uw→v(3)
There existsw∈Nv such that v,w dominates G−u, but not u, and we write vw→uTheorem 2 (see [13]).
A graphG with a cut vertex v is a 3tEC graph if and only if v is adjacent to a pendent vertex x, and for W=Nv\x and Y=V\Nv,(1)
GW is complete and W≥2(2)
GY is complete and Y≥2(3)
Every vertex inW is adjacent to Y−1 vertices in Y, and every vertex in Y is adjacent to at least one vertex in WThe following result is immediate from the above theorem.Corollary 1.
IfG is a 3tEC graph, then κG=1 if and only if δG=1; κG≥2 if and only if δG≥2.In [20], we prove the following results.Theorem 3 (see [20]).
IfG is a 3tEC graph, then αG≤κG+2, with equality only if κG=δG.Theorem 4 (see [20]).
LetG be a 3tEC graph with δG≥2. If αG≠κG+1, then G is Hamiltonian.In this paper, our main result is as follows.Theorem 5.
LetG be a 3tEC graph with δG≥2. If αG=κG+1, then G is Hamiltonian.Combining Theorems3–5, we have the following.Theorem 6.
Every3tEC graph with δG≥2 is Hamiltonian.The remainder of this paper is organized as follows. In Section2, we list some useful notations and lemmas. The proof of our main result is presented in Section 3.


## 2. Useful Lemmas

In this section, we list some useful notations and lemmas.For a3tEC graph G, if κG=1, then G contains a cut vertex. By Theorem 2, there exists a pendant vertex adjacent to such cut vertex, which means that δG=1. If δG=1, then it is clear that κG=1. Thus, we have that for a 3tEC graph G, κG=1 if δG=1. It follows that for a 3tEC graph G, if κG≠1 if δG≠1. Since 3tEC graph G that we consider is connected, κG≠0, and it does not contain isolated vertices, that is, δG≠1. It implies that for a 3EC graph G, κG≥2 if δG≥2. Corollary 1. Hence, we may assume κG≥2. Let C be a cycle. We denote by C→ the cycle C with a given orientation and by C← the cycle C with the reverse orientation. If u,v∈VC, then uC→v denotes the consecutive vertices of C from u to v in the direction specified by C→. The same vertices, in the reverse order, are given by vC←u. We use u+ to denote the successor of u and u− to denote its predecessor.LetG be a graph and C a longest cycle of G. Suppose G has no Hamilton cycle and H is any component of G−C. We set(1)NCH=X=x1,x2,…,xk,A=a1,a2,…,ak,whereai=xi+,B=b1,b2,…,bk,wherebi=xi+1−,Ci=aiC→bi.Letxi,xj∈X with i≠j. xiHxj denotes a longest xi,xj-path with the internal vertices in VH. The following Lemmas 1–4 can be found in [21], which play an important role in our proof.Lemma 1 (see [21]).
Letai,aj∈Abi,bj∈B,resp. with i≠j. Then, there is no path in G−VC−ai,aj∪VH, G−VC−bi,bj∪VH,resp. connecting ai and aj (bi and bj, resp.).Lemma 2 (see [21]).
For anyh∈VH, both A∪h and B∪h are independent sets.Lemma 3 (see [21]).
Letai,aj∈A with i≠j. For any vertex v∈ai+C→aj−, if vai∈EG, then v−aj∉EG.Lemma 4 (see [21]).
Letai∈A and bj∈B with i≠j+1. For any vertex v∈aj+1C→xi, if vbj∈EG, then v−ai∉EG. Similarly, for any vertex v∈xj+1C→bi−1, if vbj∈EG, then v+ai∉EG.In [22], Simmons obtained the following result.Lemma 5 (see [22]).
LetG be a 3tEC graph with δG≥2 and T a cut vertex of G. Then, ωG−T≤T+1.We give the following useful lemma.Lemma 6.
IfW is an independent set of k≥3 vertices of a 3tEC graph G, then there exist an ordering w1,w2,…,wk of the vertices of W and a path x1x2,…,xk−1 in VG\W such that wixi→wi+1 for i=1,2,…,k−1.Proof.
First, we show the first part of the statement. SinceW is an independent set of G, it is a clique of G¯W. For any two vertices u,v∈W, since k≥3, u,v is not a total dominating set of G+uv. By Theorem 1, if there exists a vertex x∈VG with ux→v, then we orient uv from u to v, and if there exists a vertex x∈VG with vx→u, we orient it from v to u in G¯W. Now, G¯W becomes a tournament under this orientation. By Rédei theorem [1], let w1w2,…,wk be a directed Hamilton path of G¯W. For an integer i∈1,…,k−1, we consider wi and wi+1. By our convention, there exists a neighbor xi of wi such that wixi→wi+1. Thus, xi∈VG\W.
Now, we show thatxi≠xj, for any i,j∈1,2,…,k−1 with for each i≠j. Since wjxj→wj+1, xjwj+1∉EG. On the contrary, since wixi→wi+1 and wi+1≠wj+1, xiwj+1∈EG. This implies that xi≠xj.
Sincewixi→wi+1 and xi+1≠wi+1, xixi+1∈EG. This proves x1x2,…,xk−1 is a path in G−W.


## 3. Proof of Theorem5

LetG be a graph and C a longest cycle of G. Suppose G has no Hamilton cycle and H is any component of G−C. We consider the following two cases separately to complete the proof.Case 1.
κG=2.
SupposeG has no Hamilton cycle, and let C be a longest cycle of G. Since αG=κG+1, αG=3. By Lemma 2, NCH≤2. If NCH=1, then κG=1. This contradicts κG=2. Thus,(2)NCH=2for any componentHofG−C.Claim 1.
IfCi≥2, then aibi∈EG for each 1≤i≤2.Proof.
First, we show that ifC1≥2, then a1b1∈EG; otherwise, we suppose that a1b1∉EG. Since αG=3, by Lemma 2, we have C2≥2 and a2b1,a1b2∈EG. Since a1,b1,h is an independent set, where h∈H, we have a1,b1⇒C2. This implies that there is some vertex v∈C2 such that vb1,v+a1∈EG, which contradicts Lemma 4. Hence, we have a1b1∈EG if C1≥2. Similarly, if C2≥2, then a2b2∈EG.Claim 2.
For anyu∈C1 with a1u+∈EG and v∈C2 with a2v+∈EG, uv∉EG; for any u∈C1 with b1u−∈EG and v∈C2 with b2v−∈EG, uv∉EG.Proof.
Otherwise,uC←a1u+C→x2Hx1C←v+a2C→vu is a cycle longer than C, a contradiction. By symmetry, for any u∈C1 with b1u−∈EG and v∈C2 with b2v−∈EG, uv∉EG.Claim 3.
For each vertexv∈Ci\ai,aiv∈EG, and for each vertex v∈Ci\bi,biv∈EG, where i=1,2.Proof.
Without loss of generality, we show that, for each vertexv∈C1a1,a1v∈EG. By contradiction, assume that y is the last vertex in C→a1+,b1 which is not adjacent to a1; thus, a1y∉EG. If a2y∈EG, then x2C←y+a1C→ya2C→x1Hx2 is a cycle longer than C, a contradiction. We have a2y∉EG. Thus, a1,y,a2,h is an independent set of four vertices which contradicts αG=3, where h∈H.Claim 4.
ωG−C=1.Proof.
Suppose to the contrary thatH′ is another component of G−C. Take h∈Handh′∈H′. Since αG=3, we have NCH′∩A≠∅; otherwise, A∪h,h′ is an independent set of four vertices. Similarly, NCH′∩B≠∅. By Lemma 1, we may assume NCH′∩A=a1. If b2∈NCH′, then C′=a1C→b2H′a1 is a cycle not less than C, and H0=H∪x1 is a component of G−C′, but a1,b2,x2⊆NC′H0, NC′H0≥3, which contradicts (2). Hence, we have b1∈NCH′. By the maximality of C, we have C1≥3. By Claims 1, 2, and 3, we have a1+a2∉EG; thus, a1+,a2,h,h′ is an independent set of four vertices which contradicts αG=3. Thus, we have ωG−C=1.Claim 5.
ωG−T−H=1, where T=x1,x2.Proof.
By Lemma5 and Claim 4, we have ωG−T−H≤2. If ωG−T−H=2, then EC1,C2=∅. Consider a1 and h, a1h∉EG, where h∈H. a1,h is not a domination set of G since a1,h cannot dominate C2. By Theorem 1, there exists a vertex x such that a1x→h or xh→a1. If a1x→h, then x∈Na1 and x∈C1\a1, but this is impossible since C2 is not dominated. Thus, xh→a1, we have x=x2, and hence,(3)x2⇒VG\a1,x1.
Considera2 and h, a2h∉EG. a2,h cannot dominate G since C1 is not dominated; by Theorem 1, there exists a vertex x such that a2x→h or hx→a2. If a2x→h, then x∈C2\a2, but this is impossible since C1 is not dominated. Thus, hx→a2, we have x=x1, and hence,(4)x1⇒VG\a2,x2.
Considerb1 and b2, b1b2∉EG, and b1,b2 cannot dominate G since VH is not dominated; by Theorem 1, there exists a vertex z such that b1z→b2 or b2z→b1. If b1z→b2, in order to dominate VH, then z=x2, but this is impossible because of (3). If b2z→b1, then z=x1, but this is impossible because of (4). Thus, we get ωG−T−H=1.Claim 6.
EC1,C2=a1b2,a2b1.Proof.
By Claim5, we have EC1,C2≠∅. By Claims 2 and 3, we have EC1,C2⊆a1b2,a2b1. Assume a1b2∈EG; by Lemma 1, Ci≥2 for i=1,2. We now show that a2b1∈EG. If a2b1∉EG, then a2,b1 cannot dominate G since VH is not dominated, and there exists a vertex z such that a2z→b1 or b1z→a2. If a2z→b1, then z dominates VH, so z=x1. We have a2x1→b1 and a2x1∈EG, but a2x1∉EG by Lemma 3, a contradiction. If b1z→a2, then z=x1, and a1b2C←x2Hx1b1C←a1 is a cycle longer than C, a contradiction. Thus, a2b1∈EG. Hence, EC1,C2=a1b2,a2b1.
By Claim6, we have Ci≥3 for i=1,2. Otherwise, we suppose that C1=2; then, a1x1Hx2b1a2C→b2a1 is a cycle longer than C, a contradiction. By symmetry, we have C2≥3. Consider a1 and a2, a1,a2 cannot dominate G, and without loss of generality, there exists a vertex y such that a1y→a2; in order to dominate VH, then y=x1 and a1x1→a2. By Claims 2 and 3, x1⇒C2\a2,b2, and hence, x1Hx2a2b1C←a1b2C←a2+x1 is a cycle longer than C, a contradiction. Thus, G has a Hamilton cycle.Case 2.
κG≥3.
LetG be a graph and C a longest cycle of G. Suppose G has no Hamilton cycle and H is a component of G−C. Set NGH∩VC=X, and define A,B,andCi as before; then, κG≤k. By Lemma 2, αG≥k+1. We have κG≥k since αG=κG+1. Thus, κG=k.
ConsideringA and h, where h∈H, by Lemma 2, A∪h is an independent set. Let T=y1y2,…,yk−1 be the path of A defined in Lemma 6. Since A≥3, by Lemma 6, we have aiyi→ai+1 and hai∉EG for i=1,2,…,k−1; then, yiai∈EG and yih∈EG. Thus, y1,…,yk−1⊆Nh and yi∈X. We may assume aijxij→aij+1, 1≤j≤k−1. Thus, we can obtain that VH⊆NGxij for 1≤j≤k−1. Take u∈NGxik∩VH. Since aijxij→aij+1 and uaij∉EG, we have uxij∈EG; then, u∈∩i=1kNGxi∩VH, that is,(5)uxi∈EG,for1≤i≤k.Claim 7.
A∪B≥k+1.Proof.
IfA∪B=k, then Ci=1 for 1≤i≤k. Since ai1xi1→ai2, ai2xi1∉EG. By Lemma 2, NGai2∩VC⊆X; thus, NGai2∩VC≤k−1. Since κG=k, there exists a component H′ of G−C such that NGai2∩VH′≠∅ and NCH′∩VC≥k. By Lemma 1, there is no path in G−VC−ai,aj∪VH connecting ai and aj, so NGH′∩VC⊆X∪ai2\xi2,xi2+1, which implies that κG≤k−1, a contradiction. Thus, we get A∪B≥k+1.Claim 8.
There exist a vertexv∈A∪B and a vertex z such that vz→u, where u is the vertex specified in (5).Proof.
For anyv∈A∪B, uv∉EG, and u,v cannot dominate G; thus, there exists a vertex z such that uz→v or vz→u. For vi,vj∈A∪B with vi≠vj, i≠j, if there exist vertices zi,zj such that uzi→vi and uzj→vj, then we claim that zi≠zj. Otherwise, we set zi=zj=z. Since uz→vi and uvj∉EG, zvj∈EG, but uz→vj, and we have zvj∉EG; this is impossible; thus, zi≠zj. For every vi∈A∪B, if there exists a vertex zi such that uzi→vi, then zi∈Nu and zi∈X, but this is impossible since A∪B≥k+1 and X=k. Thus, there exist a vertex v∈A∪B and a vertex z such that vz→u.
By symmetry, we may assume thata1z→u. Obviously, z∉X.Claim 9.
Ifa1z→u, then z=bk.Proof.
Sincea1z→u, aiz∈EG for 1≤i≤k, and by Lemma 1, we can assume that z∈Ci. Since κG≥3 and A is an independent set, we have z∉A.
Ifi≠k, then we show that z∉Ci\ai,bi. Otherwise, we suppose z∈Ci\ai,bi; then, z+∉X and z+u∉EG. Since a1z→u and a1ai+1∉EG, zai+1∈EG. By Lemma 3, we have z+aj∉EG for j≠i+1. If z+ai+1∈EG, we have zbi+1∉EG by Lemma 4; hence, a1bi+1∈EG. Note that a1z→u and zai+1,a1bi+1∈EG; thus, there exists a vertex v∈Ci+1 such that vz∈EG and v+a1∈EG, but uxi+1C←z+ai+1C→vzC←a1v+C→x1u is a cycle longer than C, a contradiction. Hence, z+ai+1∉EG. A∪z+,u is an independent set of G with k+2 vertices; hence, α≥k+2, again a contradiction.
Ifi≠k, then z≠bi. Otherwise, we have a1bi→u and a1bi+1,biai+1∈EG. This implies that there exists a vertex v∈Ci+1 such that vbi∈EG and v+a1∈EG, which contradicts Lemma 4. Thus, z≠bi for i≠k, and z∉X\x1.
Ifi=k and z≠bk, then we have z+∉X, and hence, z+u∉EG. Since a1z→u, za1∈EG. By Lemma 4, we get z+bj,z−bj∉EG for j≠k. If z+z−∈EG, then ux2C←a1za2C→z−z+C→x1u is a cycle longer than C, a contradiction. Hence, z+z−∉EG. B∪u,z+,z−\bk is an independent set of k+2 vertices; hence, α≥k+2, again a contradiction. Thus, we have z=bk and a1bk→u.
By symmetry, ifaiz→u, then z=bi−1 for any 2≤i≤k.
By Claim9, we have a1bk→u, a1bk∈EG. Thus, by Lemma 2, we have C1≥2 and Ck≥2 which imply A∪B≥k+2. Since a1bk∈EG, by Lemma 3, we have x1aj∉EG for j≠1, and x1bi∉EG for i≠k. Thus, we have Nx1∩A∪B\a1,bk=∅. Since k≥3, by Lemma 2, we can see that, for any vertex v∈A∪B, ux1→v is impossible. For any v∈A∪B\a1,bk, considering u and v, uv∉EG, and u,v cannot dominate G. So, there exists a vertex z such that uz→v or vz→u. If for any vi,vj∈A∪B\a1,bk, vi≠vj for i≠j, there exist vertices ziandzj such that uzi→vi and uzj→vj, then by the same analogous argument to the proof of Claim 8, we have zi≠zj. For every v∈A∪B\a1,bk, if there exists a vertex z such that uz→v, then we have z∈X\x1, but this is impossible since A∪B\a1,bk≥k and X\x1=k−1. Thus, there exist a vertex v∈A∪B\a1,bk and a vertex z such that vz→u. Assume, without loss of generality, that v∈A, say v=al. Since Nx1∩A∪B\a1,bk=∅ and alz→u, z≠bl−1, which contradicts Claim 9.
The proof of Theorem5 is completed. We show that every 3tEC graph with δG≥2 and αG=κG+1 has a Hamilton cycle. Combining Theorems 3–5, we show that every 3tEC graph with δG≥2 is Hamiltonian.



---

*Source: 5523761-2021-04-21.xml*