# Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles

Authors: Zh. G. Nikoghosyan
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

In 1974, Goodman and Hedetniemi proved that every 2-connected(K1,3,K1,3+e)-free graph is hamiltonian. This result gave rise many other conditions for Hamilton cycles concerning various pairs and triples of forbidden connected subgraphs under additional connectivity conditions. In this paper we investigate analogous problems when forbidden subgraphs are disconnected which affects more global structures in graphs such as tough structures instead of traditional connectivity structures. In 1997, it was proved that a single forbidden connected subgraph R in 2-connected graphs can create only a trivial class of hamiltonian graphs (complete graphs) with R=P3. In this paper we prove that a single forbidden subgraph R can create a non trivial class of hamiltonian graphs if R is disconnected: (∗1) every (K1∪P2)-free graph either is hamiltonian or belongs to a well defined class of non hamiltonian graphs; (∗2) every 1-tough (K1∪P3)-free graph is hamiltonian. We conjecture that every 1-tough (K1∪P4)-free graph is hamiltonian and every 1-tough P4-free graph is hamiltonian.


---

## Body

## 1. Introduction

Only finpite undiprected graphs without loops or multiple edges are considered. LetG be a graph with vertex set V(G) and edge set E(G). We write G[S] for the subgraph of G induced by S. The neighborhood of a vertex x∈V(G) will be denoted by N(x). We use n to denote the number of vertices (order) of G. The independence number of G, denoted by α, is the maximum size of an mutually nonadjacent vertices in G. If H1,…,Ht(t≥1) are graphs then a graph G is said to be (H1,…,Ht)—free if G contains no copy of any of the graphs H1,…,Ht as an induced subgraph; the graphs H1,…,Ht will be also referred to in this context as forbidden subgraphs. We denote by Pi and Ci the path and the cycle on i vertices. Further, Kn denotes the complete graph of order n, and Ka,b denotes the complete bipartite graph with partite sets of cardinalities a and b. Specifically, the graph K1,3 will be called a claw. The graph K1,3+e is obtained from K1,3 by adding an edge. Let Ni,j,k be the graph which is obtained by identifying each vertex of a triangle with an end vertex of one of three vertex-disjoint paths of lengths i,j,k. Let s(G) denote the number of components of a graph G. A graph G is t-tough if |S|≥ts(G∖S) for every subset S of the vertex set V(G) with s(G∖S)>1. The toughness of G, denoted τ(G), is the maximum value of t for which G is t-tough (taking τ(Kn)=∞ for all n≥1). A good reference for any undefined terms is [1].The first sufficient condition for hamiltonicity of a graph in terms of forbidden subgraphs is by Goodman and Hedetniemi [2].Theorem A (see [2]).
Every 2-connected(K1,3,K1,3+e)-free graph is hamiltonian.This result gave rise to many other hamiltonicity conditions for various pairs and triples of forbidden connected subgraphs under additional connectivity conditions.In 1997, Faudree and Gould [3] proved that a single forbidden connected subgraph R in 2-connected graphs can create only a trivial class (complete graphs) of hamiltonian graphs with R=P3.Theorem B (see [3]).
LetR be a connected graph and let G be a 2-connected graph. Then G is R-free implies G is hamiltonian if and only if R=P3.
The following theorem presents the forbidden pairs version of Theorem B.Theorem C (see [3]).
LetR and S be connected graphs (R,S≠P3) and G be a 2-connected graph of order n≥10. Then G is (R,S)-free implies G is Hamiltonian if and only if R=K1,3 and S is one of the graphs:
(1)P4,P5,P6,N0,0,0,N0,0,1,N0,0,2,N0,1,1,N0,0,3,N0,1,2,N1,1,1.The forbidden triple version of Theorems B and C still is not known.In this paper we investigate analogous problems when forbidden subgraphs are disconnected which affects more global structures in graphs such as tough structures instead of traditional connectivity structures.First of all, we prove that a single forbidden subgraphR can create a non trivial class of hamiltonian graphs if R is disconnected. As starting point, we consider K1∪K1 and K1∪K1∪K1 as disconnected sugraphs consisting of two and three isolated vertices, respectively. In other words, K1∪K1 is a compliment of K2 and K1∪K1∪K1 is a complement of K3 (a triangle). The first proposition follows immediately.Proposition 1.
Every(K1∪K1)-free graph is complete and therefore is hamiltonian.The next proposition shows that(K1∪K1∪K1)-free graphs are hamiltonian if and only if they are 2-connected.Proposition 2.
Every 2-connected(K1∪K1∪K1)-free graph is hamiltonian.Observe thatK1∪P2 is the minimal forbidden disconnected subgraph containing at least one edge. To describe the hamiltonian graphs with forbidden subgraph (K1∪P2), we need the following recursive definition.Definition 3.
We say thatG∈ℵ if and only if either V(G) is independent set of vertices or G is complete graph or there is a bipartition V(G)=V1∪V2 such that(1)
N(v)=V2 for each v∈V1,(2)
G[V2]∈ℵ.By the Definition, if G is a complete bipartite graph then G∈ℵ.Theorem 4.
IfG is a (K1∪P2)–free graph then either G is Hamiltonian or G∈ℵ with α(G)>n/2.IfG is a 1-tough graph then by the definition, α(G)≤n/2. Hence, the following holds from Theorem 4 immediately.Corollary 5.
Every 1-tough(K1∪P2)-free graph is hamiltonian.This result can be slightly improved.Theorem 6.
Every 1-tough(K1∪P3)-free graph is hamiltonian.Theorem6 is sharp in some respects. Indeed, K2,3 is a nonhamiltonian (K1∪P3)-free (even (K1∪P2)-free) graph with τ(K2,3)=2/3 and κ(K2,3)=2, implying that the condition “G is 1-tough” in Theorem 6 cannot be removed or replaced by “G is 2-connected.” Now form a graph, denoted by H1, by adding a new vertex x7 to C6=x1x2x3x4x5x6x1 and new edges x7x1,x7x4,x2x6,x2x4,x4x6. Since H1 is a nonhamiltonian (K2∪P3)-free graph with τ(H1)=1, we can claim that the condition “G is (K1∪P3)-free” in Theorem 6 cannot be relaxed to “G is (K2∪P3)-free.” Finally, H1 is a (K1∪K1,3)-free graph and hence the condition “G is (K1∪P3)-free” in Theorem 6 cannot be relaxed to “G is (K1∪K1,3)-free.” So, Theorem 6 is best possible in many respects. The condition “G is (K1∪P3)-free” in Theorem 6 perhaps can be relaxed to “G is (K1∪P4)-free.”Conjecture 7.
Every 1-tough(K1∪P4)-free graph is hamiltonian.Conjecture7 (if true) is best possible in all respects. Indeed, the above constructed graph H1 shows that the condition “G is (K1∪P4)-free” in Conjecture 7 cannot be replaced by “G is (K1∪P5)-free.”Moreover, the following seems reasonable as well.Conjecture 8.
Every 1-toughP4-free graph is hamiltonian.For more than one tough graphs, we conjecture the following.Conjecture 9.
Every(K1∪P5)-free graph with τ>1 is hamiltonian.The Petersen graph shows that the condition “G is (K1∪P5)-free” in Conjecture 9 cannot be replaced by “G is (K1∪P6)-free”.The next conjecture concerns(K2∪K2)-free graphs.Conjecture 10.
Every(K2∪K2)-free graph with τ>1 is hamiltonian.
The graphH1 (see the graph examples concerning the sharpness of Theorem 6) shows that the condition τ>1 in Conjecture 10 can not be replaced by τ=1. Further, the Petersen graph shows that the condition “G is (K2∪K2)-free” in Conjecture 10 can not be replaced by “G is (K2∪K3)-free”.The next conjecture is based on a forbidden subgraphK1∪K1,3 containing the claw K1,3 as a substructure.Conjecture 11.
Every(K1∪K1,3)-free graph with τ>4/3 is hamiltonian.The Petersen graph shows that the conditionτ>4/3 in Conjecture 11 can not be replaced by τ=4/3.


## 2. Additional Notation and Preliminaries

ForS a subset of V(G), we denote by G∖S the subgraph of G induced by V(G)∖S. For a subgraph H of G we use G∖H short for G∖V(H). Furthermore, for a subgraph H of G and x∈V(G), we define NH(x)=N(x)∩V(H).A simple cycle (or just a cycle)C of length t≥2 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. A graph G is hamiltonian if G contains a Hamilton cycle, that is, a cycle of length n. A cycle C in G is dominating if G∖C is edgeless.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. The expression Q=xQ→y means that x,y are the endvertices of Q. For x∈V(C), we denote the hth successor and the hth predecessor of x on C→ by x+h and x-h, respectively. We abbreviate x+1 by x+. For each X⊂V(C), we define X+h={x+h∣x∈X}.To prove Proposition2 and Theorems 4, 6, we need the following useful lemma.Lemma 12.
LetG be a 2-connected graph, C→ a longest cycle in G with a given orientation and x∈V(G∖C). Let P1→,P2→ be two internally disjoint paths with given orientations starting at x and terminating on C at different vertices u,v. Then u+v+∉E(G).


## 3. Proofs

Proof of Lemma12.
Assume the contrary, that isu+v+∈E(G). Then
(2)uP1←xP2→vC←u+v+C→u
is longer than C, contradicting the fact that C is a longest cycle in G. Hence, u+v+∉E(G). Lemma 12 is proved.Proof of Proposition2.
SinceG is 2-connected graph, it contains a cycle. Let C→ be a longest cycle in G with a given orientation. If V(G∖C)=∅ then C is a Hamilton cycle and we are done. Let V(G∖C)≠∅ and let  x∈V(G∖C). Since G is 2-connected, there are two internally disjoint paths P1,P2 with given orientations starting at x and terminating on C at different vertices u,v. If xu+∈E(G) then uP1←xu+C→u is longer than C, contradicting the fact that C is a longest cycle. Hence, xu+∉E(G). Analogously, xv+∉E(G). Furthermore, by Lemma 12, u+v+∉E(G), implying that {x,u+,v+} is an independent set of vertices which contradicts the fact that G is (K1∪K1∪K1)-free graph. This final contradiction proves that G is hamiltonian. Proposition 2 is proved.Proof of Theorem4.
LetG be a (K1∪P2)-free graph. If V(G) is independent set of vertices, then by the definition, G∈ℵ with α(G)=n>n/2 and we are done. Let G contain at least one edge. Next, if G is disconnected, then clearly G contains K1∪P2 as an induced subgraph, contradicting the hypothesis. Let G be connected. Further, if G is a tree, then clearly G either is a star (i.e., G is a complete bipartite graph and hence G∈ℵ with α(G)=n-1>n) or contains K1∪P2 as an induced subgraph, again contradicting the hypothesis. Now assume that  G is not a tree and let C=v1v2...vtv1 be a longest cycle in G with a given orientation. If V(G∖C)=∅, then C is a Hamilton cycle and we are done. Let V(G∖C)≠∅. Since G is connected, we have xy∈E(G) for some x∈V(G∖C) and y∈V(C). Assume without loss of generality that y=v1. Since C is a longest cycle, we have xv2∉E(G). If xv3∉E(G), then x and v2v3 form an induced subgraph K1∪P2, contradicting the hypothesis. Hence xv3∈E(G). By a similar argument, xvi∈E(G) for each i=1,3,5,…,t-1 and xvi∉E(G) for each i=2,4,6,...,t where t is even. Further, since C is a longest cycle, by Lemma 12, {x,v2,v4,…,vt} is an independent set of vertices. Moreover, for each u,v∈{x,v2,v4,…,vt}, there is no path connecting u and v and passing through V(G)∖(V(C)∪{x}).
To prove thatN(x)={v1,v3,...,vt-1}, assume the contrary, that is xz∈E(G) for some z∈V(G)∖(V(C)∪{x}). Recalling that C is a longest cycle, we conclude that zv2∉E(G) and zv3∉E(G). Therefore, z and v2v3 form a disconnected subgraph K1∪P2 which contradicts the fact that G is (K1∪P2)-free. Hence N(x)⊆V(C). But then it is not hard to see that V(G∖C) is an independent set of vertices.
Now let us prove  thatN(v)={v1,v3,...,vt-1} for each v∈V(G∖C). Assume that v≠x. Since V(G∖C) is an independent set of vertices, we have N(v)⊆V(C). if v2v∈E(G), then as above v4v∈E(G), implying that
(3)v1xv3v2vv4C→v1
is longer than C, a contradiction. Let v2v∉E(G). But then (as above) v1v∈E(G), implying that N(v)={v1,v3,...,vt-1}. Put
(4)V1=V(G∖C)∪{v2,v4,…,vt},V2={v1,v3,…,vt-1}.
Clearly V(G)=V1∪V2 Since V1 is an independent set of vertices and |V1|>|V2|, we can state that α(G)≥|V1|>n/2 and thus G is not hamiltonian. It remains to prove that G∈ℵ. If V2 is independent or G[V2] is complete, then G∈ℵ and we are done. Otherwise denote by V3 a largest independent subset in V2 and put V4=V2∖V3. Clearly, |V3|≥2 and V4≠∅. Let w2 be any vertex in V4. Since V3 is a largest independent set, there exists a vertex w1∈V3 such that w1w2∈E(G). Let w3∈V3∖{w1}. If w2w3∉E(G), then w3 and w1w2 form an induced subgraph K1∪P2, contradicting the hypothesis. Hence w2w3∈E(G) implying that w2v∈E(G) for each v∈V3. This means also that each vertex in V4 is adjacent to all vertices in V3. Applying the same arguments to V4 instead of V2, we conclude that G∈ℵ.Proof of Theorem6.
LetG be a 1-tough (K1∪P3)-free graph. In particular, G is 2-connected graph and therefore contains a cycle. Let C be a longest cycle in  G with a given orientation. If V(G∖C)=∅ then C is a Hamilton cycle and we are done. Let  V(G∖C)≠∅ and let H be a connected component of G∖C of maximum order. Denote by ξ1,...,ξs the elements of NC(H) occurring on C in a consecutive order. Since G is 1-tough, we have s≥2. Set
(5)Ii=ξiC→ξi+1,Ii*=ξi+C→ξi+1-(i=1,2,…,s),
where ξs+1=ξ1. Since C is a longest cycle in  G, we have |V(Ii)|≥3 and |V(I*i)|≥1 for each i∈{1,2,...,s}. The segments I1,I2,…,Is are called elementary segments on C induced by NC(H). We call a path L=zL→w an intermediate path between two distinct elementary segments Ia and Ib if
(6)z∈V(Ia*),w∈V(Ib*),V(L)∩V(C∪H)={z,w}.
DefineΥ(Ii1,Ii2,…,Iit) to be the set of all intermediate paths between elementary segments Ii1,Ii2,…,Iit. If Υ(I1,I2,…,Is)=∅, then G∖{ξ1,…,ξs} has at least s+1 connected components, contradicting the fact that G is 1-tough. Otherwise Υ(Ia,Ib)≠∅ for some distinct a,b∈{1,…,s}. Choose a path L=xL→y in Υ(Ia,Ib) such that x∈V(Ia*) and y∈V(Ib*). If |V(L)|≥3, then each vertex v∈V(H) with the subpath of L of length 2 forms an induced subgraph K1∪P3, contradicting the hypothesis. Let |V(L)|=2, that is, L=xy and hence Υ(I1,I2,…,Is)⊆E(G). Put
(7)Q=ξa+C→xyC←ξb+.
Assume without loss of generality that L is chosen from Υ(Ia,Ib) such that |V(Q)| is minimum. Since C is a longest cycle in G, by Lemma 12, {ξ1,…,ξs}+ is an independent set of vertices, implying that either x≠ξa+ or y≠ξb+, say x≠ξa+. Since |V(Q)| is minimum, we have x-y∉E(G), that is, x-xy forms an induced subgraph P3. But then each vertex v∈V(H) with x-xy forms an induced K1∪P3, again contradicting the hypothesis. Theorem 6 is proved.



---

*Source: 673971-2013-03-10.xml*