Wei Zhenga,b,c, Hajo Broersma^c , Ligong Wang^b

^aSchool of Mathematics and Statistics, Shandong Normal University,

Jinan, Shandong, 250358, P.R. China

^bSchool of Mathematics and Statistics, Northwestern Polytechnical University,

Xi'an, Shaanxi, 710129, P.R. China

^cFaculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

zhengweimath@163.com, h.j.broersma@utwente.nl, lgwangmath@163.com

Let ω(G) denote the number of components of a graph G. A connected graph G is said to be 1-tough if ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. It is well-known that every hamiltonian graph is 1-tough, but that the reverse statement is not true in general, and even not for triangle-free graphs. We present two classes of triangle-free graphs for which the reverse statement holds, i.e., for which hamiltonicity and 1-toughness are equivalent. Our two main results give partial answers to two conjectures due to Nikoghosyan.

Keywords: toughness, 1-tough, forbidden subgraph, hamiltonicity, triangle-free graph

Mathematics Subject Classification : 05C38, 05C42, 05C45

DOI: 10.5614/ejgta.2021.9.2.15

1. Introduction

All graphs we consider are finite, simple and undirected graphs. For terminology, notation and concepts not defined here, we refer the reader to [2]. A cycle in a graph G is called a Hamilton cycle if it contains all vertices of G, and G is called hamiltonian if it contains a Hamilton cycle.

Hamiltonicity has been a central topic in structural graph theory since the 1950s, and has regained more popularity since the development of algorithmic graph theory and the discovery that

Received: 7 June 2019, Revised: 23 March 2021, Accepted: 13 April 2021.

the associated decision problem is NP-complete. It also has many and sometimes very surprising applications, as the recent publication [5] in this journal shows. Forbidden subgraph conditions for guaranteeing hamiltonian properties have been studied intensively since the PhD thesis of Bedrossian [1] appeared in 1991. For more recent work on forbidden subgraph conditions we refer to the publication [6] in the first issue of this journal and the references therein.

The research we report here is inspired by several conjectures on the hamiltonicity of graphs presented by Nikoghosyan in the paper [8]. A central concept in that paper is the toughness of graphs, so we first recall the essential definitions related to toughness.

Let ω(G) denote the number of components of a graph G. As it is defined in [4], a connected graph G is said to be t-tough if t · ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. The toughness of G, denoted by τ (G), is the maximum value of t such that G is t-tough (taking τ (Kn) = ∞ for all n ≥ 1).

It is an easy exercise to show that every hamiltonian graph is 1-tough, but that the reverse statement does not hold. Nikoghosyan [8] investigated the hamiltonicity of 1-tough graphs by considering disconnected single forbidden subgraphs, and he presented the following conjectures. Here we use 4 to denote a complete graph on 3 vertices, G¹ ∪ G² to denote the disjoint union of two vertex-disjoint graphs G¹ and G2, and kG to denote the graph consisting of k disjoint copies of the graph G. For a fixed graph H, a graph G is called H-free if G does not contain an induced copy of H, i.e., a set S ⊆ V (G) such that the graph on vertex set S containing all edges of G between pairs of vertices in S is isomorphic to H. The latter is also called an induced subgraph and denoted by hSi.

Conjecture 1 (Nikoghosyan [8]). Every 1-tough K¹ ∪ P4-free graph on at least three vertices is hamiltonian.

In an attempt to prove this conjecture, Li et al. [7] left one open case, as expressed in the following two results.

Theorem 1.1 (B. Li et al. [7]). Let R be an induced subgraph of P4, K¹ ∪ P³ or 2K¹ ∪ K2. Then every R-free 1-tough graph on at least three vertices is hamiltonian.

Note that every induced subgraph of K¹ ∪ P⁴ is also an induced subgraph of P4, K¹ ∪ P³ or 2K¹ ∪ K2, except for K¹ ∪ P⁴ itself.

Theorem 1.2 (B. Li et al. [7]). Let R be a graph on at least three vertices. If every R-free 1-tough graph on at least three vertices is hamiltonian, then R is an induced subgraph of K¹ ∪ P4.

These two results together imply the following. While forbidding any proper subgraph of K¹ ∪ P⁴ can guarantee 1-tough graphs (on at least three vertices) to be hamiltonian, the case with the graph K¹ ∪ P⁴ itself is still open. Since Conjecture 1 seems to be very hard to resolve, we considered partial solutions. In particular, if we impose the additional condition that the graphs under consideration are triangle-free, we can prove the following partial result.

Theorem 1.3. Every 1-tough {4, K¹ ∪ P4}-free graph on at least three vertices is hamiltonian.

We postpone the proof of Theorem 1.3 to Section 3.

Another conjecture in [8] deals with the hamiltonicity of K¹ ∪ K1,3-free graphs. Clearly, Theorem 1.2 implies that the toughness of these graphs must be strictly larger than one.

Conjecture 2 (Nikoghosyan [8]). Every K¹ ∪ K1,3-free graph G on at least three vertices with τ (G) > 4/3 is hamiltonian.

In [8], the Petersen graph was used to show that the condition τ (G) > 4/3 in Conjecture 2 cannot be relaxed to τ (G) = 4/3. Similarly as in Theorem 1.3, we involved the triangle as a second forbidden subgraph, and obtained the following result related to Conjecture 2.

Theorem 1.4. If G is a 1-tough {4, K¹ ∪ K1,3}-free graph on at least three vertices, then G is hamiltonian or the Petersen graph.

The proof of Theorem 1.4 is postponed to Section 4. In [8], Nikoghosyan also raised the following conjecture.

Conjecture 3 (Nikoghosyan [8]). Every 2K2-free graph G on at least three vertices with τ (G) > 1 is hamiltonian.

As far as we know, this conjecture is still open, but it is known from a recent paper due to Shan [9] that 3-tough 2K2-free graphs on at least three vertices are hamiltonian. This result considerably improves the result due to Broersma et al. [3] that 25-tough 2K2-free graphs on at least three vertices are hamiltonian. A partial result in [3] deals with triangle-free 2K2-free graphs, and supplements our results, as follows.

Theorem 1.5 (Broersma et al. [3]). If G is a 1-tough {4, 2K2}-free graph on at least three vertices, then G is hamiltonian.

Another open conjecture from [8] states that every K¹ ∪ P5-free graph G on at least three vertices with τ (G) > 1 is hamiltonian. By involving triangle-freeness, we propose the following conjecture for future work.

Conjecture 4. If G is a 1-tough {4, K¹ ∪ P5}-free graph on at least three vertices, then G is hamiltonian.

Before we give our proofs of Theorems 1.3 and 1.4, we first provide some additional notation and terminology.

2. Some notation and terminology

Let G be a graph with vertex set V (G) and edge set E(G). For a vertex u ∈ V (G) and subgraphs H and R of G, let NR(u) and NR(H) denote the set of neighbors of the vertex u and the subgraph H in R, respectively, that is

\[N_R(u) = \{ v \in V(R) \mid uv \in E(G) \},\]

On hamiltonicity of 1-tough triangle-free graphs Wei Zheng et al.

\[N_R(H) = \left(\bigcup_{u \in V(H)} N_R(u)\right) \setminus V(H).\]

The numbers \(|N_R(u)|\) and \(|N_R(H)|\) are respectively called the degree of the vertex u and the degree of the subgraph H in R, and denoted as \(d_R(u)\) and \(d_R(H)\), respectively. If R = G, then we use N(u) and N(H) instead of \(N_R(u)\) and \(N_R(H)\), and \(N_R(H)\), and \(N_R(H)\) instead of \(N_R(u)\) and \(N_R(H)\), respectively.

Let \(C=x_1x_2\cdots x_tx_1\) be a cycle of length \(t\geq 3\) in G with a given orientation. For a vertex \(x_i\in V(C)\) \((1\leq i\leq t)\), we let \(x_i^{-l},x_i^{+l}\) \((1\leq i-l< i+l\leq t)\) denote the vertices \(x_{i-l}\) and \(x_{i+l}\) on C, respectively. Instead of \(x_i^{-1}\) and \(x_i^{+1}\), we simply use \(x_i^{-}\) and \(x_i^{+}\) to denote the immediate predecessor and successor of \(x_i\) on C, respectively. For two vertices \(x_i,x_j\in V(C),x_iCx_j\) denotes the subpath of C from \(x_i\) to \(x_j\), and \(x_j\overline{C}x_i\) denotes the path from \(x_j\) to \(x_i\) in the reverse direction. For any \(I\subseteq V(C)\), let \(I^-=\{x_i^-\mid x_i\in I\}\) and \(I^+=\{x_i^+\mid x_i\in I\}\). A similar notation is used for paths.

Recall that for a subset S of V(G), we use \(\langle S \rangle\) to denote the subgraph of G induced by S. If the induced subgraph \(\langle S \rangle\) is isomorphic to a graph H, then we slightly abuse the notation by writing \(S \cong H\). We use \(\{u; v, w, x\}\) to denote the graph isomorphic to the \(claw \ K_{1,3}\) induced by \(\{u, v, w, x\}\) with edge set \(\{uv, uw, ux\}\), and we call u the center, and v, w, x the end vertices of this claw.

3. Proof of Theorem 1.3

Suppose, to the contrary, that G is a 1-tough \(\{\triangle, K_1 \cup P_4\}\)-free graph on at least three vertices, but not hamiltonian. Then G contains a cycle. We choose a longest cycle C of G. Since G is not hamiltonian, we use H to denote a component of G - V(C). We denote all neighbors of H on C as \(N_C(H) = \{u_1, u_2, \ldots, u_t\}\) with \(t \geq 2\), in this order around C according to a fixed orientation of C, and we denote the (vertex set of the) segment of C from \(u_i^+\) to \(u_{i+1}^-\) as \(S_i = u_i^+ C u_{i+1}^-\) for \(i = 1, 2, \ldots, t\). The next result is obvious, but we give it and its proof for later reference.

Claim 1. \(N_C(H)^+\) and \(N_C(H)^-\) are independent, and there is no path outside C connecting any two vertices of any one of these two sets.

Proof. Without loss of generality, assume that \(u_i^+\) and \(u_j^+\) are connected by a path P outside C (possibly P is an edge). We find a cycle longer than C: \(u_i H u_j \overline{C} u_i^+ P u_j^+ C u_i\), a contradiction. \(\square\)

We continue with proving another set of claims that are more specific for this graph class. We say that two sets A and B are connected by a path outside C if there is a path between a vertex \(x \in A\) and \(y \in B\) with all internal vertices not on C.

Let \(S_i\) and \(S_j\) be two distinct segments.

Claim 2. If \(S_i\) and \(S_j\) are connected by a path outside C, then \(\{u_j^{+2}, u_j^{+4}, \dots, u_{j+1}^{-2}\} \subseteq N(u_i^+)\) and \(\{u_i^{+2}, u_i^{+4}, \dots, u_{i+1}^{-2}\} \subseteq N(u_j^+)\), and \(|S_i|\) are odd.

Proof. Suppose \(S_i\) and \(S_j\) are connected by a path outside C. Then we can find a shortest path from \(u_i^+\) to \(u_i^+\) along \(u_i^+CxPy\overline{C}u_i^+\), where \(x \in S_i\), \(y \in S_i\) and P is a path such that \(V(P) \cap\)\((V(C) \cup V(H)) = \{x, y\}\). We use \(P_{ij}\) to denote this shortest path for segments \(S_i\) and \(S_j\). Then \(P_{ij}\) is an induced path. If \(|V(P_{ij})| \geq 4\), then any vertex of H together with a subpath of \(P_{ij}\) of length 3 induces a copy of \(K_1 \cup P_4\), contradicting the hypothesis. Using Claim 1, \(|V(P_{ij})| = 3\). Thus, P is a path with \(x = u_i^+\) or \(y = u_i^+\). Denote \(P_{ij} = p_1 p_2 p_3\), with \(p_1 = u_i^+\) and \(p_3 = u_i^+\). Since P is a path outside C connecting \(S_i\) and \(S_j\), and by Claim 1, we have that \(p_2 \in S_i \cup S_j\), and \(|S_i| > 1\) or \(|S_j| > 1\). Without loss of generality, we assume \(|S_i| > 1\). If \(p_2 \neq u_i^{+2}\), then to avoid any vertex \(w \in V(H)\) with the path \(u_i^{+2}u_i^{+}p_2u_i^{+}\) inducing \(K_1 \cup P_4\), we have \(p_2u_i^{+2} \in E(G)\). Then \(\{u_i^+, u_i^{+2}, p_2\} \cong \triangle\), a contradiction. Hence, \(u_i^+ u_i^{+2} \in E(G)\). If \(u_i^{+4}\) exists, then to avoid inducing triangles and to avoid any vertex \(w \in V(H)\) with the path \(u_i^+ u_i^{+2} u_i^{+3} u_i^{+4}\) inducing \(K_1 \cup P_4\), we have \(u_i^+u_i^{+4} \in E(G)\). Similarly, we have \(u_i^{+6}, u_i^{+8}, \ldots \in N(u_j^+)\) if these vertices exist. For the last vertex of \(S_i\), if \(u_j^+u_{i+1}^- \in E(G)\), then \(u_j^+ \neq u_{j+1}^-\) by Claim 1. To avoid any vertex \(w \in V(H)\) with the path \(u_i^+ u_i^{+2} u_i^+ u_i^{+2}\) inducing \(K_1 \cup P_4\), we have \(u_i^+ u_i^{+2} \in E(G)\). Then there is a cycle longer than C: \(u_i H u_{i+1} C u_i^+ u_{i+1}^- \overline{C} u_i^+ u_j^{+2} C u_i\), a contradiction. Hence, \(u_j^+ u_{i+1}^- \notin E(G)\) and \(|S_i|\) is odd. If \(u_j^{+2}, u_j^{+4}, u_j^{+6}, \ldots\) exist, then by symmetry, we have that \(u_j^{+2}, u_j^{+4}, u_j^{+6}, \ldots \in N(u_i^+)\) and \(|S_j|\) is

For any segment \(S_i\) that is connected to another segment by a path outside C, by Claim 2 we know that \(|S_i|\) is odd. We divide \(S_i\) into two sets: \(S_i^o = \{u_i^+, u_i^{+3}, \dots, u_{i+1}^-\}\) and \(S_i^e = \{u_i^{+2}, u_i^{+4}, \dots, u_{i+1}^{-2}\}\). By Claim 2, if \(S_i\) is connected to \(S_j\) by a path outside C, then \(S_i^e \subseteq N(u_j^+)\), and since G is \(\triangle\)-free, \(S_i^o \cap N(u_j^+) = \emptyset\).

Claim 3. If \(S_i\) and \(S_j\) are connected by a path outside C, then \(S_i^o \cup S_j^o\) is independent.

Proof. Suppose that \(u_i^{+s}, u_i^{+t} \in S_i^o\) (t > s) and \(u_i^{+s}u_i^{+t} \in E(G)\). Since G is \(\triangle\)-free, t > s + 2, and since \(u_i^{+(s+1)}, u_i^{+(t-1)} \in N(u_j^+), u_i^{+s+1}u_i^{t-1} \notin E(G)\). Then any vertex \(w \in V(H)\) with the path \(u_i^{s+1}u_i^{+s}u_i^{+t}u_i^{+(t-1)}\) induces a copy of \(K_1 \cup P_4\), contradicting the hypothesis. Hence, \(S_i^o\) is independent. Similarly, \(S_j^o\) is also independent.

independent. Similarly, \(S_j^o\) is also independent. Suppose that \(u_i^{+l} \in S_i^o, u_j^{+m} \in S_j^o\) and \(u_i^{+l}u_j^{+m} \in E(G)\). By Claim 2, \(u_i^{+l} \neq u_i^+, u_j^{+m} \neq u_j^+\) and \(u_j^{+(m-1)}u_i^+ \in E(G)\). Also we know that \(u_i^{+(l+1)} = u_{i+1}\) or \(u_i^{+(l+1)}u_j^+ \in E(G)\). Then the cycle \(u_i H u_j \overline{C} u_i^{+(l+1)} u_j^+ C u_j^{+(m-1)} u_i^+ C u_i^{+l} u_j^{+m} C u_i\) is longer than C, a contradiction.

Claim 4. If \(S_i\) is connected to \(S_j\) by a path outside C, and \(S_i\) has a neighbor \(w' \in V(G) \setminus (V(C) \cup V(H))\), then \(S_i^e \subseteq N(w')\) and \(S_i^o \cap N(w') = \emptyset\).

Proof. First, \(u_i^+ \notin N(w')\); otherwise, to avoid any vertex \(w \in V(H)\) with a path \(w'u_i^+u_j^{+2}u_j^+\) (if \(|S_j| \neq 1\)) or with a path \(w'u_i^+u_i^{+2}u_j^+\) (if \(|S_i| \neq 1\)) inducing \(K_1 \cup P_4\), we have \(w'u_j^+ \in E(G)\). That contradicts Claim 1. Suppose that \(u_i^{+k} \in N(w')\) (\(k \neq 1\)). To avoid any vertex \(w \in V(H)\) with a path \(w'u_i^{+k}u_i^{+(k+1)}u_i^{+(k+2)}\) or with a path \(w'u_i^{+k}u_i^{+(k-1)}u_i^{+(k-2)}\) inducing \(K_1 \cup P_4\), we have \(w'u_i^{+(k+2)} \in E(G)\) and \(w'u_i^{+(k-2)} \in E(G)\) if these vertices exist. By this argumentation, we know that every vertex on \(S_i\) having even distance to \(u_i^{+k}\) on C is a neighbor of w'. Since \(u_i^+ \notin N(w')\) and G is \(\triangle\)-free, \(S_i^e \subseteq N(w')\) and \(S_i^o \cap N(w') = \emptyset\). □

We use \(S^o\) to denote the union of all \(S^o_i\), and \(S^e\) to denote the union of all \(S^e_i\), for all segments \(S_i\) (\(1 \le i \le t\)) that are connected to some other segment by a path outside C. By Claim 3 and Claim 4, there is no path outside C connecting any two vertices of \(S^o\). Hence, if we remove all the vertices of \(N_C(H) \cup S^e\), we get at least \(|N_C(H) \cup S^e| + 1\) components, contradicting the hypothesis that G is 1-tough. This completes the proof of Theorem 1.3.

4. Proof of Theorem 1.4

Let G be a 1-tough \(\{\triangle, K_1 \cup K_{1,3}\}\)-free graph on at least three vertices. For any vertex \(u \in V(G)\) of degree larger than 2, since G is \(\triangle\)-free, we have that u and any three of its neighbors together induce a \(K_{1,3}\). Next we distinguish two cases according to the connectivity of G in order to complete the proof of Theorem 1.4.

Case 1. G is 3-connected.

Suppose that G is not hamiltonian. Using a number of claims, we are going to prove that G is the Petersen graph. Here we use the same notations as in the proof of Theorem 1.3. Let C be a longest cycle of G, let H be a component of G - V(C), and let \(N_C(H) = \{u_1, u_2, \ldots, u_t\}\) be all the neighbors of H on C, in this order according to a fixed orientation of C. Since G is 3-connected, \(t \geq 3\). We denote the segment of C from \(u_i^+\) to \(u_{i+1}^-\) as \(S_i = u_i^+ C u_{i+1}^-\) for \(i = 1, 2, \ldots, t\). Claim 1 in the proof of Theorem 1.3 clearly also holds here, but we recall it here without proof for later reference.

Claim 5. \(N_C(H)^+\) and \(N_C(H)^-\) are independent, and there is no path outside C connecting any two vertices of any one of these two sets.

We present several other claims, each followed by a proof.

Claim 6. If \(S_i\) and \(S_j\) are connected by a path \(P_{ij}\) outside C, then \(P_{ij} = u_i^+ u_{i+1}^-\) or \(P_{ij} = u_{i+1}^- u_i^+\).

Proof. Let \(P_{ij} = p_1 p_2 \dots p_s\) \((s \ge 2)\) be such a path with \(p_1 \in S_i\) and \(p_s \in S_j\). If \(p_1 \notin \{u_i^+, u_{i+1}^-\}\) or \(p_s \notin \{u_j^+, u_{j+1}^-\}\), then \(\{w, p_1, p_1^-, p_1^+, p_2\} \cong K_1 \cup K_{1,3}\) and \(\{w, p_s, p_s^-, p_s^+, p_{s-1}\} \cong K_1 \cup K_{1,3}\) for any vertex \(w \in V(H)\), a contradiction. By Claim 5, if \(p_1 = u_i^+\), then \(p_s = u_{j+1}^-\); if \(p_1 = u_{i+1}^-\), then \(p_s = u_j^+\) \((j \ne i+1)\). In both cases, \(|S_i| \ge 2\) and \(|S_j| \ge 2\). To avoid any vertex of V(H) with \(\{u_i^+; u_i, u_i^{+2}, p_2\}\) or \(\{u_j^+; u_j, u_j^{+2}, p_{s-1}\}\) inducing \(K_1 \cup K_{1,3}\), we have \(V(H) \subseteq N(u_i)\) or \(V(H) \subseteq N(u_j)\). Since G is △-free, |V(H)| = 1 and \(N_C(H)\) is independent. Denote \(H = \{w\}\).

Suppose \(s \geq 3\) and \(p_2 \in V(H')\), where H' is another component of G - V(C) different from H. If \(P_{ij}\) is connecting \(u_i^+\) to \(u_{j+1}^-\), then \(u_i \neq u_{j+1}\), and \(p_2u_i \notin E(G)\), \(p_2u_{j+1} \notin E(G)\); otherwise there clearly is a longer cycle. Then to avoid \(p_2\) with \(\{w; u_i, u_j, u_{j+1}\}\) inducing \(K_1 \cup K_{1,3}\), we have \(p_2u_j \in E(G)\). Since \(\{u_i^{+2}, u_j^+\} \in N_C(H')^+, u_i^{+2}u_j^+ \notin E(G)\) by Claim 5. To avoid \(u_j^+\) with \(\{u_i^+; u_i, u_i^{+2}, p_2\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_j^+u_i \in E(G)\). Then \(u_i^-u_j^+ \notin E(G)\); otherwise \(\{u_i, u_i^-, u_j^+\} \cong \Delta\). To avoid \(u_i^-\) with \(\{u_j; u_j^-, u_j^+, w\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_i^-u_j \in E(G)\). Then we find a cycle longer than C: \(u_iwu_{j+1}Cu_i^-u_j\overline{C}u_i^+P_{ij}u_{j+1}^-\overline{C}u_j^+u_i\), a contradiction. If \(P_{ij}\) is connecting \(u_{i+1}^-\) to \(u_j^+\), then \(u_{i+1} \neq u_j\) and \(p_2u_{i+1} \notin E(G)\), \(p_2u_j \notin E(G)\). We have \(p_2u_i \in E(G)\); otherwise, \(p_2\) with \(\{w; u_i, u_{i+1}, u_j\}\) induces \(K_1 \cup K_{1,3}\). By Claim 5, \(u_i^+u_{i+1} \notin E(G)\) since \(\{u_i^+, u_{i+1}\} \in N_C(H')^+\). To avoid \(u_{i+1}\) with \(\{u_i; u_i^+, u_i^-, p_2\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_{i+1}u_i^- \in E(G)\). Then \(u_{i+1}^+u_i^- \notin E(G)\); otherwise \(\{u_i^-, u_{i+1}, u_{i+1}^+\} \cong \Delta\).

To avoid \(u_{i+1}^+\) with \(\{u_i; u_i^-, u_i^+, w\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_{i+1}^+ u_i \in E(G)\). Then the cycle \(u_{i+1}wu_j\overline{C}u_{i+1}^+u_iCu_{i+1}^-P_{ij}u_j^+Cu_i^-u_{i+1}\) is longer than C, a contradiction. Hence, s=2 and \(P_{ij}=u_i^+u_{j+1}^-\) or \(P_{ij}=u_{i+1}^-u_j^+\).

Since G is 1-tough, there are two distinct segments \(S_i\) and \(S_j\) that are connected by a path outside C. By Claim 6, \(u_i^+u_{j+1}^-\in E(G)\) or \(u_{i+1}^-u_j^+\in E(G)\). To avoid any vertex of V(H) with \(\{u_i^+;u_i,u_i^{+2},u_{j+1}^-\}\) or with \(\{u_j^+;u_j,u_j^{+2},u_{i+1}^-\}\) inducing \(K_1\cup K_{1,3}\), we have \(V(H)\subseteq N(u_i)\) or \(V(H)\subseteq N(u_j)\). Since G is \(\triangle\)-free, |V(H)|=1 and \(N_C(H)\) is independent. Denote \(H=\{w\}\).

Claim 7. \(|S_i| = 2\) for all \(i \in \{1, 2, ..., t\}\).

Proof. Suppose that there is a segment \(S_i\) with \(i \in \{1, 2, ..., t\}\) such that \(|S_i| \geq 3\). Then \(u_i^+ \neq u_{i+1}^{-2}\). By Claim 6, \(u_{i+1}^{-2}\) has no neighbor in \(V(C) \setminus (S_i \cup N_C(H))\). To avoid \(u_{i+1}^{-2}\) with \(\{u_{i+2}; u_{i+2}^-, u_{i+2}^+, w\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_{i+1}^{-2} u_{i+2} \in E(G)\). To avoid \(u_i^-\) with \(\{u_{i+1}^{-2}; u_{i+1}^-, u_{i+1}^{-3}, u_{i+2}\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_i^- u_{i+2} \in E(G)\). To avoid \(u_{i+1}^-\) with \(\{u_{i+2}; u_{i+2}^-, u_i^-, w\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_{i+1}^- u_{i+2} \in E(G)\). But now \(\{u_{i+1}^{-2}, u_{i+1}^-, u_{i+2}\} \cong \Delta\), a contradiction. Hence, \(|S_i| \leq 2\) for all \(i \in \{1, 2, ..., t\}\).

Suppose that there is a segment \(S_i\) with \(i \in \{1,2,\ldots,t\}\) such that \(|S_i|=1\). Then \(u_i^+=u_{i+1}^-\). By Claim 5 and Claim 6, \(u_i^+\) has no neighbor in \(V(C)\setminus N_C(H)\). To avoid \(u_i^+\) with \(\{u_j;u_j^-,u_j^+,w\}\) inducing \(K_1\cup K_{1,3}\) (\(j\neq i+1, j\neq i-1\)), we have \(u_i^+u_j\in E(G)\) for all \(j\in \{1,2,\ldots,t\}\). Since G is 1-tough, there are two segments \(S_j\) and \(S_k\) (k>j) that are connected by an edge \(u_j^+u_{k+1}^-\) or \(u_{j+1}^-u_k^+\). Since \(|S_i|\leq 2\) for all \(i\in \{1,2,\ldots,t\}\) and by Claim 5, \(|S_j|=|S_k|=2\) in both cases. If \(u_j^+u_{k+1}^-\in E(G)\), then to avoid \(u_j^+\) with \(\{u_k;u_k^+,u_i^+,w\}\) inducing \(K_1\cup K_{1,3}\), we have \(u_j^+u_k\in E(G)\). Since G is \(\Delta\)-free, \(k\neq j+1\) and \(u_{j+1}^-u_k\notin E(G)\). Then \(u_{j+1}^-\) with \(\{u_k;u_k^-,u_i^+,w\}\) induces a \(K_1\cup K_{1,3}\), a contradiction. If \(u_{j+1}^-u_k^+\in E(G)\), then k>j+1. To avoid \(u_{j+1}^-\) with \(\{u_k;u_k^-,u_i^+,w\}\) inducing \(K_1\cup K_{1,3}\), we have \(u_{j+1}^-u_k\in E(G)\), but then \(\{u_{j+1}^-,u_k,u_k^+\}\cong \Delta\), a contradiction. Hence, \(|S_i|=2\) for all \(i\in \{1,2,\ldots,t\}\).

Claim 8. For any component \(H' \neq H\) of G - V(C), \(N_C(H') = N_C(H)\).

Proof. Suppose that H' has a neighbor in \(V(C) \setminus N_C(H)\). By Claim 7, this neighbor of H' is either \(u_i^+\) or \(u_i^-\) for some \(i \in \{1, 2, \dots, t\}\). Without loss of generality, we assume that \(w'u_1^+ \in E(G)\), where \(w' \in V(H')\). By Claim 5, \(w'u_2^+ \notin E(G)\). To avoid \(u_2^+\) with \(\{u_1^+; u_1, u_1^{+2}, w'\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_1u_2^+ \in E(G)\). To avoid \(u_3^+\) with \(\{u_1; u_1^+, u_2^+, w\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_1u_3^+ \in E(G)\). To avoid \(u_2^{+2}\) with \(\{u_1; u_1^+, u_3^+, w\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_1^+u_2^{+2} \in E(G)\). We also have \(w'u_2^{+2} \notin E(G)\); otherwise, \(\{w', u_1^+, u_2^{+2}\} \cong \triangle\), a contradiction. But now w with \(\{u_1^+; u_1^{+2}, u_2^{+2}, w'\}\) induces \(K_1 \cup K_{1,3}\), a contradiction. Hence, \(N_C(H') \subseteq N_C(H)\). Since we have chosen H arbitrarily, by symmetry we have \(N_C(H) \subseteq N_C(H')\). Hence, \(N_C(H') = N_C(H)\). □

Claim 9. t = 3.

Proof. Since G is 1-tough, there are at least two distinct segments that are connected by a path outside C. By Claim 6 and Claim 7, without loss of generality, we can assume \(u_1^+u_i^- \in E(G)\) \((i \geq 3)\). To avoid \(u_i^+\) with \(\{u_1^+; u_1, u_2^-, u_i^-\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_1u_i^+ \in E(G)\) or \(u_2^-u_i^+ \in E(G)\). If \(u_1u_i^+ \in E(G)\), then \(u_{i+1} \neq u_1\) and \(u_{i+1}^-u_1 \notin E(G)\). To avoid \(u_{i+1}^-\) with

\(\{u_1^+; u_1, u_2^-, u_i^-\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_{i+1}^- u_1^+ \in E(G)\). But then w with \(\{u_1^+; u_2^-, u_i^-, u_{i+1}^-\}\) induces a \(K_1 \cup K_{1,3}\), a contradiction. Hence, \(u_1 u_i^+ \notin E(G)\). Suppose that \(u_2^- u_i^+ \in E(G)\). If \(i \neq t\), then \(u_{i+1}^- \neq u_1^-\). To avoid \(u_i^+\) with \(\{u_1; u_1^+, u_1^-, w\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_i^+ u_1^- \in E(G)\). But then w with \(\{u_i^+; u_1^-, u_2^-, u_{i+1}^-\}\) induces a \(K_1 \cup K_{1,3}\), a contradiction. Hence, i = t.

If \(i \neq 3\), then \(u_{i-1} \neq u_2\). To avoid \(u_2^+\) with \(\{u_1^+; u_1, u_2^-, u_i^-\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_2^+u_i^- \in E(G)\) or \(u_2^+u_1 \in E(G)\). If \(u_2^+u_i^- \in E(G)\), then w with \(\{u_i^-; u_1^+, u_2^+, u_{i-1}^+\}\) induces a \(K_1 \cup K_{1,3}\), a contradiction. If \(u_2^+u_1 \in E(G)\), then \(u_3^-u_1 \notin E(G)\). To avoid \(u_3^-\) with \(\{u_1^+; u_1, u_2^-, u_i^-\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_3^-u_1^+ \in E(G)\). Then w with \(\{u_1^+; u_2^-, u_3^-, u_i^-\}\) induces a \(K_1 \cup K_{1,3}\), a contradiction. Hence, i = t = 3.

Since G is 1-tough and by Claims 5–9, without loss of generality, we can assume that \(u_1^+u_3^- \in E(G)\). To avoid \(u_3^+\) with \(\{u_1^+; u_1, u_2^-, u_3^-\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_2^-u_3^+ \in E(G)\). To avoid \(u_1^-\) with \(\{u_3^-; u_3, u_2^+, u_1^+\}\) inducing \(K_1 \cup K_{1,3}\), we have \(u_1^-u_2^+ \in E(G)\). By Claims 5–9, there is no other edge joining a pair of nonadjacent vertices on G. Suppose that \(H' \neq H\) is another component of G - V(G). By Claim 8, \(N_C(H') = \{u_1, u_2, u_3\}\). Assume that \(w' \in V(H')\) and \(w'u_1 \in E(G)\). Then \(u_3^+\) with \(\{u_1; u_1^+, w, w'\}\) induces a \(K_1 \cup K_{1,3}\), a contradiction. Hence, H is the only component of G - V(G). Recalling that |V(H)| = 1, it is clear that G is the Petersen graph. This completes the proof for Case 1.

Case 2. \(\kappa(G) = 2\).

Suppose that \(\{u_1, u_2\}\) is a cut set of G. Since G is 1-tough, \(G - \{u_1, u_2\}\) has exactly two components, say \(H_1\) and \(H_2\). Since G is \(\{\triangle, K_1 \cup K_{1,3}\}\)-free, each of \(H_1\) and \(H_2\) is an induced path or an induced cycle. We again prove a number of claims in order to complete the proof.

Claim 10. If \(H_i\) is an induced cycle C' for \(i \in \{1, 2\}\), then there are two consecutive vertices on C' such that one vertex is adjacent to \(u_1\) and the other one is adjacent to \(u_2\).

Proof. Suppose, by contradiction, that for any neighbor of \(u_1\) on C', its predecessor and successor on C' are not adjacent to \(u_2\). Since G is \(\triangle\)-free, any two vertices of \(N_{H_i}(u_1) \cup N_{H_i}(u_2)\) are not consecutive on C'. Since C' is induced, by removing all the vertices of \(N_{H_i}(u_1) \cup N_{H_i}(u_2)\) from G we get \(|N_{H_i}(u_1) \cup N_{H_i}(u_2)| + 1\) components, contradicting the hypothesis that G is 1-tough. \(\square\)

Claim 11. If \(H_i\) is an induced path P for \(i \in \{1, 2\}\), then one end vertex of P is adjacent to \(u_1\) and the other one is adjacent to \(u_2\).

Proof. Suppose that \(H_1=P=p_1p_2\dots p_t\). If \(t\leq 2\), then the claim clearly holds. Suppose that \(t\geq 3\) and \(\{p_1,p_t\}\in N(u_1)\setminus N(u_2)\). Let \(p_i\in V(H_1)\) (1< i< t) be a vertex adjacent to \(u_2\). If \(u_1u_2\in E(G)\), then there is a vertex \(x\in V(H_2)\) such that \(xu_2\notin E(G)\). Then x with \(\{p_i;p_{i-1},p_{i+1},u_2\}\) induces a \(K_1\cup K_{1,3}\), a contradiction. Thus, \(u_1u_2\notin E(G)\). If \(|V(H_2)|\geq 2\), then there will also be a vertex in \(H_2\) not adjacent to \(u_2\), and similarly we can get an induced \(K_1\cup K_{1,3}\). Hence, \(|V(H_2)|=1\). Denote \(V(H_2)=\{w\}\). If \(t\geq 6\), then \(p_3u_1\in E(G)\) and \(p_4u_1\in E(G)\); otherwise, \(p_3\) or \(p_4\) with \(\{u_1;p_1,p_t,w\}\) induces \(K_1\cup K_{1,3}\), a contradiction. Now \(\{u_1,p_3,p_4\}\cong \Delta\), a contradiction. If t=5, then to avoid \(p_3\) with \(\{u_1;p_1,p_t,w\}\) inducing \(K_1\cup K_{1,3}\), we have \(p_3u_1\in E(G)\). To avoid \(u_2\) with \(\{u_1;p_1,p_3,p_t\}\) inducing \(K_1\cup K_{1,3}\), we have \(p_3u_2\in E(G)\). To avoid inducing a triangle, \(\{p_2,p_4\}\cap (N(u_1)\cup N(u_2))=\emptyset\). Obviously, now \(\{u_1,p_3\}\) is a cut set

Using Claim 10 and Claim 11, it is clear that there is a cycle in G containing all the vertices of G. Hence, G is hamiltonian. This completes the proof of Theorem 1.4.

Acknowledgement

This paper is supported by the National Natural Science Foundation of China (No. 11871398), the Natural Science Basic Research Plan in Shaanxi Province of China (No. 2018JM1032) and the China Scholarship Council (No. 201706290168).

References

• [1] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity, Thesis, Memphis State University, USA, 1991.
• [2] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Graduate Texts in Mathematics, vol. 244 (2008).
• [3] H.J. Broersma, V. Patel, and A. Pyatkin, On toughness and hamiltonicity of 2K2-free graphs, J. Graph Theory, 75 (2014) 244–255.
• [4] V. Chvatal, Tough graphs and hamiltonian circuits, ´ Discrete Math., 5 (1973) 215–228.
• [5] M. Haythorpe and A. Johnson, Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples, Electron. J. Graph Theory Appl., 7 (1) (2019) 61–75.
• [6] B. Li, H.J. Broersma, and S. Zhang, Forbidden subgraphs for traceability of block chains, Electron. J. Graph Theory Appl., 1 (1) (2013) 1–10.
• [7] B. Li, H.J. Broersma, and S. Zhang, Forbidden subgraphs for hamiltonicity of 1-tough graphs, Discuss. Math. Graph Theory, 36 (2016) 915–929.
• [8] Zh.G. Nikoghosyan, Disconnected forbidden subgraphs, toughness and hamilton cycles, ISRN Combinatorics, 2013, Article ID 673971 (2013) 4 pages.
• [9] S. Shan, Hamiltonian cycles in 3-tough 2K2-free graphs, J. of Graph Theory, 94 (2020) 349– 363.