A related problem on $s$-Hamiltonian line graphs

1.   Introduction

For the notation or terminology not defined here, see ^[1]. A graph is called trivial if it has only one vertex, nontrivial otherwise. Let $\kappa'(G)$ represent the edge-connectivity of a graph $G$. An edge (vertex) cut $X$ is essential if $G-X$ has at least two non-trivial components. A graph $G$ is essentially $k$-edge-connected (or essentially $k$-connected) if $G$ does not have an essential edge cut $X$ (or an essential vertex cut $X$) with $|X| < k$. For a connected graph, define $ess(G) = \max\{k: G \text{is essentially}\; k -{\rm{connected}}\}$. For any $u\in V(G)$, we use $N_{G}(u)$ to denote the set of vertices which are adjacent to $u$ in the graph $G$ and define $d_G(u) = |N_{G}(u)|$, $N_G[u] = N_G(u)\cup \{u\}$. For an integer $i\geq0$, define $D_{\geq i}(G) = \{v\in V(G): d_G(v)\geq i\}$, $D_{\leq i}(G) = \{v\in V(G): d_G(v)\leq i\}$, $D_{i}(G) = \{v\in V(G): d_G(v) = i\}$ and $d_i(G) = |D_i(G)|$. We use $H\subseteq G$ ($H\cong G$) to denote the fact that $H$ is a subgraph of $G$ ($H$ and $G$ are isomorphic). Define $G[S]$ is the subgraph induced in $G$ by $S$ for $S\subseteq V(G)$ or $S\subseteq E(G)$. For $H_1, H_2\subseteq G$, two disjoint sets $S_1, S_2\subseteq V(G)$ and $X\subseteq E(G)$, define $G-S_1 = G[V(G)-S_1]$, $G-X = G[E(G)-X]$, $[S_1, S_2]_G = \{uv\in E(G): u\in S_1, v\in S_2\}$, $[H_1, H_2]_G = [V(H_1), V(H_2)]_G$. We use $v$ for $\{v\}$ and $e$ for $\{e\}$. Throughout this paper, for an integer $n\geq 1$, $P_n$ denotes a path of order $n$, $C_n$ denotes a cycle on $n$ vertices, $W_n$ denotes the graph obtained from an $n$-cycle by adding a new vertex and connecting it to every vertex of the $n$-cycle, and $K_5-e$ denotes the graph obtained from $K_5$ by deleting an edge. We call a bipartite graph $K_{1, n}$ a star.

A graph is $k$-triangular if each edge is in at least $k$ triangles. The line graph of a given graph $G$, denoted by $L(G)$, is a graph with vertex set $E(G)$ such that two vertices in $L(G)$ are adjacent if and only if the corresponding edges in $G$ are incident to a common vertex in $G$. For an integer $s\geq0$, a graph $G$ is $s$-Hamiltonian if for any vertex subset $S\subset V(G)$ such that $|S|\leq s$, $G-S$ is Hamiltonian. Broersma and Veldman in ^[2] raised the following question.

Problem 1. (Broersma and Veldman, ^[2]) For an integer $k\geq0$, determine the value $s$ such that the line graph $L(G)$ of a $k$-triangular graph $G$ is $s$-Hamiltonian if and only if $L(G)$ is $(s+2)$-connected.

They commented in ^[2] that Problem 1 holds for $0\leq s\leq k$ and conjectured that it holds if $0\leq s\leq 2k$. Chen, Lai, Shiu and Li in ^[7] confirmed it holds when $0\leq s\leq \max\{2k, 6k-16\}$. Then Lai et al. gave some attempt to characterize $s$-Hamiltonian line graph. A graph $G$ is claw-free if it does not contain $K_{1, 3}$ as an induced subgraph.

Theorem 2. Let $G$ be a graph and $s\geq 2$ be an integer.

($1$) (Lai and Shao, ^[9]) For $s\geq 5$, $L(G)$ is $s$-Hamiltonian if and only if $L(G)$ is $(s+2)$-connected.

($2$) (Lai, Zhan, Zhang and Zhou, ^[11]) For $s\geq 2$, if $G$ is claw-free, then $L(G)$ is $s$-Hamiltonian if and only if $L(G)$ is $(s+2)$-connected.

In fact, the authors mainly proved the cases $s\in \{2, 3, 4\}$ of Theorem 2(2) in ^[11]. Motivated by Theorem 2(2), we propose the following conjecture.

Conjecture 3. Let $G$ be a claw-free connected graph such that $L(G)$ is 3-connected and let $s\geq1$ be an integer. If one of the following holds:

($i$) $s\in\{1, 2, 3, 4\}$ and $L(G)$ is essentially $(s+3)$-connected, or

($ii$) $s\geq5$ and $L(G)$ is essentially $(s+2)$-connected,

then for any subset $S\subseteq V(L(G))$ with $|S|\leq s$, $|D_{\leq1}(L(G)-S)|\leq\left \lfloor \frac{s}{2} \right \rfloor$ and $L(G)-S-D_{\leq1}(L(G)-S)$ is Hamiltonian.

Define the core of $G$, denoted by $G_0$, to be the graph obtained from $G$ by deleting all the vertices of degree 1, and replacing each path $xyz$ with $y\in D_2(G)$ by an edge $xz$. It is easy to see that if $G$ is claw-free, then the core $G_0$ is claw-free. Our main result of this paper is as follows, which settles Conjecture 3$(i)$.

Theorem 4. Let $s\in \{1, 2, 3, 4\}$ and $G$ be a connected graph such that $L(G)$ is 3-connected and essentially $(s+3)$-connected and the core $G_0$ is claw-free. Then for any $S\subseteq V(L(G))$ with $|S|\leq s$, $|D_{\leq1}(L(G)-S)|\leq\left \lfloor \frac{s}{2} \right \rfloor$ and $L(G)-S-D_{\leq1}(L(G)-S)$ is Hamiltonian.

A dominating closed trail (abbreviated DCT) in a graph $G$ is a closed trail (or, equivalently, an Eulerian subgraph) $T$ in $G$ such that every edge of $G$ has at least one vertex on $T$. The following result by Harary and Nash-Williams relates the existence of a DCT in a graph $G$ and the existence of a Hamiltonian cycle in its line graph $L(G)$.

Theorem 5. (Harary and Nash-Williams, ^[8]) Let $G$ be a graph with at least three edges. Then $L(G)$ isHamiltonian if and only if $G$ has a DCT.

Remark 1. For integer $i\in \{0, 1, 2, 3, 4\}$ and the graph $H_i$ depicted in Figure 1, let $H_i'$ be the graph obtained from $H_i$ by deleting the bold lines. Then $H_i'$ has no DCT and by Theorem 5, $L(H_i')$ is non Hamiltonian. Since $\kappa (L(H_0)) = 2$ and $ess(L(H_0)) = s+5$, the condition "$L(G)$ is 3-connected" in Theorem 4 is sharp. Furthermore, for $i\in \{1, 2, 3, 4\}$, $ess(L(H_i)) = i+2$ and $L(H_i)$ is not $i$-Hamiltonian, then the condition "$L(G)$ is essentially $(s+3)$-connected" in Theorem 4 is sharp.

2.   Proof of Theorem 4

Before starting the proof, we need some definitions and additional results. For $X\subseteq E(G)$, define the contraction $G/X$ is the graph obtained from $G$ by identifying the two ends of each edge in $X$ and then deleting the resulting loops. If $H$ is a subgraph of $G$, we write $G/H$ for $G/E(H)$. If $v_H$ is the contraction image of $H$ in $G/H$, then $H$ is called the preimage of $v$, and denoted by $PI(v)$. Call $v$ is non-trivial if $|V(PI(v))|\geq 2$; trivial, otherwise. Let $O(G)$ denote the set of odd degree vertices in $G$. A graph $G$ is eulerian if $O(G) = \emptyset$ and $G$ is connected. A graph $G$ is supereulerian if $G$ has a spanning Eulerian subgraph. Catlin in ^[3] defined collapsible graphs. A graph $G$ is collapsible if for any even subset $R$ of $V(G)$, $G$ has a connected spanning subgraph $\Gamma_R$ with $O(\Gamma_R) = R$. The reduction of $G$ is obtained from $G$ by contracting all maximal collapsible subgraphs of $G$. Let $\tau(G)$ denote the maximum number of edge-disjoint spanning trees of G. Let $F(G)$ be the minimum number of additional edges that must be added to $G$ so that the resulting graph has two edge-disjoint spanning trees. We summarize some results on Catlin's reduction method and other related facts below.

Theorem 6. Let $G$ be a connected graph and $H$, $G'$ be a collapsible subgraph and the reduction of $G$, respectively. Theneach of the following holds.

($1$) (Catlin, ^[3]) $G$ is collapsible if and only if $G/H$ iscollapsible. And $G$ is collapsible if and only if $G^\prime$ is $K_1$.

($2$) (Catlin, ^[4]) $F(G') = 2|V(G')|-2-|E(G')|$.

($3$) (Catlin, Han and Lai, ^[5]) If $F(G)\leq2$, then $G'\in \{K_1, K_2, K_{2, t}\}$ for some $t\geq 1$.

($4$) (Catlin, Lai and Shao, ^[6]) Let $k\geq1$ be an integer. Then $\kappa'(G)\geq2k$ if and only if for any edge subset $X\subseteq E(G)$ with $|X| < k$, $\tau(G-X)\geq k$.

An edge cut $X$ of $G$ is a $P_2$-edge-cut of $G$ if at least two components of $G-X$ contain $P_3$. Define $\kappa'_2(G) = \min\{|X|: X \text{is a}\; P_2 -{\rm{edge}}-{\rm{cut}} \; {\rm{of}} \; G \}$.

Lemma 7. If $G$ is 3-edge-connected with $\kappa'_2(G)\geq 4$, then $G$ is essentially 4-edge-connected.

Proof. For any edge cut $X$ of $G$ such that $G-X$ has two non-trivial components $G_1, G_2$, if both $G_1$ and $G_2$ contain $P_3$, then $X$ is a $P_2$-edge-cut and hence $|X|\geq 4$; otherwise, at least one of $G_1, G_2$ is isomorphic to $K_2$ and then $|X|\geq 4$.

The graphs $P_{i, j, k}, K_{i, j, k}\subseteq G$ are two subgraphs isomorphic to a $P_3$ and a $K_3$ such that three vertices have degree $i, j, k$ in $G$, respectively.

Lemma 8. Let $G$ be a 3-edge-connected graph and $G\notin \{K_4, W_4, K_5-e, K_5\}$. Then

(1) $G$ has no $K_{3, 3, 3}$ if $\kappa'_2(G)\geq 4$ and $G$ has no $K_{3, 3, 4}$ if $\kappa'_2(G)\geq 4$,

(2) $G$ has no $P_{3, 3, 3}$, $K_{3, 4, 4}$ and $K_{3, 3, k}$ for $k\leq5$ if $\kappa'_2(G)\geq 6$,

(3) $G$ has no $P_{3, 3, 3}$, $P_{3, 3, 4}$, $K_{3, 4, l}$ and $K_{3, 3, k}$ for $l\leq5$, $k\leq6$ if $\kappa'_2(G)\geq 7$.

Proof. Let $x_1x_2x_3\subseteq G$ and $X = [\{x_1, x_2, x_3\}, V(G)-\{x_1, x_2, x_3\}]_G$. We assume that $|X| < \min\{\kappa'_2(G), 7\}$. Let $\mathcal{D}$ be the set of components of $G-X$. Then each component of $G-\{x_1, x_2, x_3\}$ belongs to $\{K_1, K_2\}$ and hence $|\mathcal{D}|\leq2$ and $|\mathcal{D}| = 1$ if $P_2\in \mathcal{D}$. Then $|V(G)|\leq 5$ and hence $G\in \{K_4, W_4, K_5, K_5-e\}$, a contradiction. So $|X|\geq \kappa'_2(G)$ and lemma holds.

Lemma 9. Let $G$ be a claw-free graph of order at least 6 such that $\kappa'(G)\geq 3$ and $\kappa'_2(G)\geq 4$. Then there is a set of edge-disjoint triangles $\triangle(G)$ such that $D_3(G)\subseteq V(\triangle(G))$ and $D_3(G)\cap V(K)\neq\emptyset$ for each $K\in \triangle(G)$.

Proof. Since $G$ is claw-free with $\kappa'(G)\geq 3$, each vertex with degree 3 is in a triangle. Then we can choose a set of triangles $\triangle(G)$ such that $D_3(G)\subseteq V(\triangle(G))$, $D_3(G)\cap V(K)\neq\emptyset$ for each $K\in \triangle(G)$, and then

Suppose that there are two triangles $w_1u_1u_2w_1$, $w_2u_1u_2w_2\in \triangle(G)$, then $d_G(w_1) = d_G(w_2) = 3$; for otherwise, delete the triangle $w_iu_1u_2w_i$ in $\triangle(G)$ if $d_G(w_i)\geq 4$ for any $i\in \{1, 2\}$. Besides, $w_1w_2\notin E(G)$; for otherwise, replace $w_1u_1u_2w_1$, $w_2u_1u_2w_2$ by $w_1w_2u_2w_1$ in $\triangle(G)$. By Lemma 8, $\max\{d_G(u_1), \; d_G(u_2)\}\geq4$. Without loss of generality, assume that $d_G(u_2)\geq 4$ and there is a vertex $x_1\in N_G(u_2)$. Since $G[\{u_2, w_1, w_2, x_1\}]\ncong K_{1, 3}$, $[x_1, \{w_1, w_2\}]_G\neq\emptyset$. By symmetry, assume that $x_1w_1\in E(G)$.

If there is a vertex $x_2\in N_G(u_2)\backslash \{w_1, w_2, x_1\}$, then, by symmetry, $x_2w_2\in E(G)$. So $4\leq d_G(u_2)\leq 5$ and we can delete the triangle $w_1u_1u_2w_1$ and add the triangle $x_1w_1u_2x_1$ in $\triangle(G)$ if $x_1w_1u_2x_1\notin \triangle(G)$, a contradiction. Hence any two triangles of $\triangle(G)$ are edge-disjoint.

Theorem 10. Let $G$ be a connected graph such that $L(G)$ is 3-connected, essentially $k$-connected for some integer $k\geq1$. Then

(1) (Shao, ^[12]) the core $G_0$ of $G$ is uniquely defined and $\kappa'(G_0)\geq 3$,

(2) (Lai, Shao, Wu and Zhou, ^[10]) $\kappa'_2(G_0)\geq \kappa'_2(G)\geq k$.

For a connected graph $G$ and an Eulerian subgraph $T$, define $D[T] = \{uv: \{u, v\}\cap V(T)\neq\emptyset\}$.

Proof of Theorem 4. We first have $|D_{\leq1}(L(G)-S)|\leq\left \lfloor \frac{s}{2} \right \rfloor$ as $L(G)$ is 3-connected. For any $X = \{e_1, \cdots, e_s\}\subseteq E(G)$, let $E_1 = N_{G-X}[D_1(G-X)]$, $S_2 = V(E_1)\cap D_2(G-X)$. Then $E_1 = (G-X)[V(E_1)]$ and $|E_1|\leq\left \lfloor \frac{s}{2} \right \rfloor$. By Theorem 5, it suffices to prove that

Let $G_0$ be the core of $G$. By Theorem 10, $G_0$ is 3-edge-connected with $\kappa'_2(G_0)\geq s+3$ and $D_3(G_0)\subseteq D_3(G)$. It suffices to prove that for any $X = \{e_1, \cdots, e_s\}\subseteq E(G_0)$

(Since then for any $u\notin V(T)$, either $u\in S_2$ or $u\in V(G)$ has no neighbor in $D_1(G)$ and hence $T$ can be extended to an Eulerian subgraph $T'$ of $G$ satisfying (2.1).)

By Lemma 7, $G_0$ is essentially 4-edge-connected. By Lemma 9, $G_0$ has a set of edge-disjoint triangles $\triangle(G)$ such that $D_3(G)\subseteq V(\triangle(G))$ and $D_3(G)\cap V(K)\neq\emptyset$ for each $K\in \triangle(G)$. Let $\triangle'(G) = \{K\in \triangle(G): E(K)\cap X = \emptyset\}$ and $G_1 = G_0/ \triangle'(G)$. Then $G_1$ is 3-edge-connected, essentially 4-edge-connected and $\kappa'_2(G_1)\geq s+3$. Besides, $D_3(G_1)\subseteq D_3(G_0)$ since $G_0$ is essentially 4-edge-connected.

We first assume that $|V(G_1)|\leq 5$. If $G_1-X$ has no cycle, then it is isomorphic to the graph obtained from a star and some isolated vertices by subdividing some edges of star exactly once, respectively, and then the preimage of the center of the star is an Eulerian subgraph of $G$ satisfying (2.1). Then we assume that $G_1-X$ contains a longest cycle $C$. If for any 1-component $x_0$ of $G_1-X-C$, $|[x, V(C)]_{G_1}|\leq 1$, then (2.3) holds. We then assume that $|[x_0, V(C)]_{G_1}|\geq 2$ for some 1-component $x_0$ of $G_1-X-C$, then $|V(C)| = 4$, $|V(G_1)| = 5$. Let $C = ux_1vx_2u$. Then $E(G_1) = E(C)\cup \{x_0u, x_0v\}\cup X$. Then at least one vertex $u_0\in \{x_0, x_1, x_2\}$ is non-adjacent to one vertex of degree at most 2. Suppose otherwise. Then $\{x_0, x_1, x_2\}\subseteq D_{4}(G_1)$ and $s\in \{3, 4\}$. If $s = 3$, then $X = \{x_0x_1, x_0x_2, x_1x_2\}$ and $G_1\cong K_5-e$. If $s = 4$, then $G_1\cong K_5$. However, there is a $P_2$-edge-cut with order at most $s+2$, a contradiction. By symmetry, assume $u_0 = x_0$. Then $C$ is a dominating trail of $G-X$.

Thus we assume that $|V(G_1)|\geq 6$ in the proof below. Note that a triangle is collapsible. Thus it suffices to prove that

Case 1. $G_1-X$ is disconnected.

In this case, if edges $e_1, \cdots, e_s$ have same end vertices $u, v$ for any $u, v\in V(G_1)$ and $s\geq 2$, then $e_1, \cdots e_s$ are actually parallel edges. Since $G_1$ is 3-edge-connected, there are vertices $v,$ $x_1, \cdots x_s$ such that either $d_{G_1}(v) = s$ and $\{vx_1, \cdots, vx_s\} = \{e_1, \cdots, e_s\}$ or $s = 4, d_{G_1}(v) = 3$ and $\{vx_1, vx_2, vx_3\} = \{e_1, e_2, e_3\}$. Then $D_3(G_1)\subseteq \{v\}\subseteq V(G)$ and hence $G_1[N_{G_1}[v]]$ is claw-free.

Subcase 1.1. $d_{G_1}(v) = s$.

Let $(d_1, \cdots, d_s) = (d_{G_1}(x_1), \cdots, d_{G_1}(x_s))$ and $(d_1', \cdots, d_s') = (d_{G_1-v}(x_1), \cdots, d_{G_1-v}(x_s))$. If $s = 3$, then $\kappa'_2(G_1)\geq 6$. By symmetry, assume that $x_1x_2\in E(G_1)$ and $d_{G_1}(x_1)\leq d_{G_1}(x_2)$. By Lemma 8(2), $(d_1, d_2, d_3)\in \{(3, m, n): m\geq6, n\geq4\}\cup\{(4, m, n): m\geq5,$ $n\geq3\}\cup\{(m, n, t): m\geq5, n\geq5, t\geq3\}$ and then $(d_1', d_2', d_3')\in \{(2, m, n): m\geq5, n\geq3\}\cup\{(3, m, n):$ $m\geq4, n\geq2\}\cup\{(m, n, t): m\geq4, n\geq4, t\geq2\}$. Let

If $d_{G_1}(x_1) = 4$, then $\kappa'_2(G_1)\geq 7$. By symmetry, either $\{x_1x_2, x_2x_3\}\subseteq E(G_1)$ and $d_{G_1}(x_1)\leq d_{G_1}(x_2)\leq d_{G_1}(x_3)$ or $\{x_1x_2, x_3x_4\}\subseteq E(G_1)$, $d_{G_1}(x_1)\leq d_{G_1}(x_2)$ and $d_{G_1}(x_3)\leq d_{G_1}(x_4)$. We firstly assume that $\{x_1x_2, x_2x_3\}\subseteq E(G_1)$. By Lemma 8(3), $(d_1, d_2, d_3, d_4)\in \{(3, m, n, l): m\geq6, n\geq6, l\geq4\}\cup\{(m, n, l, p):$ $m\geq4, n\geq4, l\geq4, p\geq4\}\cup\{(4, m, n, 3): m\geq5, n\geq5\}\cup\{(m, n, l, 3):$ $m\geq5, n\geq5, l\geq5\}$. Let

We then assume that $\{x_1x_2, x_3x_4\}\subseteq E(G_1)$. By Lemma 8(3), $(d_1, d_2, d_3, d_4)\in \{(3, m, 3, n): m\geq6, n\geq6\}\cup\{(3, m, 4, n):$ $m\geq6, n\geq5\}\cup\{(4, m, 4, n): m\geq5,$ $n\geq5\}\cup\{(m, n, l, p): m\geq5, n\geq5, l\geq5, p\geq5\}$. Let

Note that $D_{\leq 3}(G_1-v)\subseteq \{x_1, \cdots, x_s\}$. Let $Q_1$ be the graph obtained from $G_1-v$ by adding the edge set $E'$. Then $Q_1$ is 4-edge-connected. By Theorem 6($4$), $\tau (Q_1-E') = \tau(G_1-v)\geq 2$. Therefore, $G_1-v$ is collapsible and then is supereulerian. Hence $G_1-X$ has a dominating Eulerian subgraph $T_1$ such that $V(G_1)\backslash V(T_1) = \{v\}$. Hence (2.3) holds.

Subcase 1.2. $s = 4$ and $d_{G_1}(v) = 3$.

Then $\kappa'_2(G_1)\geq 7$. By Subcase 1.1, $\tau(G_1-v)\geq 2$. Then $F(G_1-v-X)\leq 1$. Note that $\kappa'(G_1-v-X)\geq 2$ since $G_1$ is essentially 4-edge-connected. By Theorem 6($3$), $G_1-v-X$ is collapsible and hence it has a dominating Eulerian subgraph $T_2$ such that $V(G_1)\backslash V(T_2) = \{v\}$. Hence (2.3) holds.

Case 2. $G_1-X$ is connected.

Let $G'$ be the reduction of $G_1-X$.

Claim 1. If $F(G')\leq2$, then (2.3) holds.

Proof. By Theorem 6($3$), $G'\in \{K_1, K_2, K_{2, t}\}$ for some integer $t\geq2$. If $G'\cong K_{2, t}$ for some odd integer $t\geq3$, then each vertex of degree $2$ in $G'$ is trivial; for otherwise, assume that $|PI(u)|\geq 3$, then $PI(u)$ has a $P_3$ and there is a $P_2$-edge-cut $X' = [V(PI(u)), V(G_1)-V(PI(u))]_{G_1}$ with $|X'|\leq|X|+2$, a contradiction. If one vertex $u$ of degree 3 in $G'$ is non-trivial, then $X\subseteq [V(PI(u)), V(G_1)-V(PI(u))]_{G_1}$. If $s\leq2$, then there is a vertex of degree $2$, a contradiction. If $s = 3$, then there is a $P_{3, 3, 3}$, a contradiction. If $s = 4$, there is a $P_{3, 3, 4}$, a contradiction. Hence $G'\subseteq G_1-X$. If $s = 3$, then either $G'\cong K_{2, 5}$ and $G'$ has a $K_{3, 3, 5}$ or $G'\cong K_{2, 3}$ and $G_1\cong K_5-e$, a contradiction. If $s = 4$, then $G'$ either has a $P_{3, 3, 4}$ (if $t\geq 7$) or has a $K_{3, 3, 5}$ (if $t\leq 5$), a contradiction.

If $G'\in \{K_1, K_{2, t}\}$ for some even integer $t\geq2$, then $G'$ is supereulerian and then $G_1-X$ is supereulerian by Theorem 6($1$). If $G'\cong K_2 = uv$, then at least one of $u, v$ is trivial; for otherwise, $X\cup \{uv\}$ is a $P_2$-edge-cut of $G_1$ with $|X\cup \{uv\}|\leq s+1$, a contradiction. By symmetry, assume that $u$ is trivial and $PI(v)$ is collapsible. Then $u\in D_1(G_1-X)$ and $G_1-X$ has a dominating Eulerian subgraph $T_3$ such that $V(G_1)\backslash V(T_3) = \{u\}$ and (2.3) holds.

If $G'\cong v_1uv_2$, then $v_1, v_2$ are trivial and $PI(u)$ is collapsible. Then $v_1, v_2\in D_1(G_1-X)$ and $G_1-X$ has a dominating Eulerian subgraph $T_4$ such that $V(G_1)\backslash V(T_4) = \{v_1, v_2\}$ and (2.3) holds.

Let $G_2 = G'\cup X$ and define $\phi(G_2) = 2|V(G_2)|-|E(G_2)|-2$. Then $G_2$ is 3-edge-connected, essentially 4-edge-connected with $\kappa'_2(G_2)\geq s+3$. By Theorem 6(2), $F(G')\leq\phi(G_2)+s = \frac{1}{2}(d_3(G_2)-\sum_{i\geq5}(i-4)d_i(G_2))+(s-2)$. By Claim 1, it suffices to prove that $F(G')\leq2$, that is,

If $|D_3(G_2)|\leq 2$ when $s = 3$, then add at most one edge $e$ such that $D_3(G_2)\subseteq V(e)$ and the resulting graph, say $G_2'$, is 4-edge-connected. Then $\tau(G_2) = \tau(G_2'-\{e, f\})\geq 2$ for any edge $f\in E(G_2')$ by Theorem 6($4$) and hence $F(G')\leq F(G_2-X)\leq 2$. By the same argument, $F(G')\leq 2$ if $|D_3(G_2)|\leq 6$ when $s = 1$, $|D_3(G_2)|\leq4$ when $s = 2$ and $|D_3(G_2)| = 0$ when $s = 4$. Hence we only consider the cases $|D_3(G_2)|\geq 3$ when $s = 3$ and $|D_3(G_2)|\geq 1$ when $s = 4$.

Note that $D_3(G_2)\subseteq V(G)$. Then $G_2[N_{G_2}[u]]$ is claw-free for any $u\in D_3(G_2)$ and then $u$ is in a triangle of $G_2$. Recall $G_2$ is obtained from $G'$ by adding $X$, then each vertex of degree 3 is in a triangle of $G_2$ which contains at least one edge of $X$. Then $G_2$ has at most $s$ edge-disjoint triangles containing all vertices of degree 3 and each of them must contain at least one edge of $X$. Since $\kappa'_2(G_2)\geq 5$, $G_2$ has no $K_{3, 3, 3}$. Then $|D_3(G_2)|\leq 2s$.

Besides, for any vertex $u\in V(G_2)$ with degree less than $s+2$,

(For otherwise, $[V(PI(u)), V(G_1)-V(PI(u))]_{G_1}$ is a $P_2$-edge-cut of $G_1$, a contradiction.) We then consider the following two subcases to finish our proof.

Subcase 2.1. $s = 3$ and $3\leq |D_3(G_2)|\leq 6$.

Then $\kappa'_2(G_2)\geq 6$ and it suffices to prove that

By Lemma 8(2), there is a triangle $x_1x_2x_3x_1$ such that $\max\{d_{G_2}(x_1), d_{G_2}(x_2), d_{G_2}(x_3)\} \geq 5$ if $|D_3(G_2)| = 3$ and $d_{G_2}(x_1) = d_{G_2}(x_2) = 3$, $d_{G_2}(x_3)\geq6$ if $|D_3(G_2)| = 4$, and hence (2.6) holds.

If $|D_3(G_2)| = 5$, then there are three edge-disjoint triangles $u_1x_1x_2u_1, u_2y_1y_2u_2, u_3z_1z_2u_3$ such that $\{x_1, x_2, y_1, y_2, z_1\} = D_3(G_2)$ and $d_{G_2}(u_1)\geq 6$, $d_{G_2}(u_2)\geq 6$ and $d_{G_2}(u_3)\geq 5$. So (2.6) holds if at least two of $u_1, u_2, u_3$ are distinct or $d_{G_2}(z_2)\geq 5$. Otherwise, $G_2[N_{G_2}[z_2]]$ is claw-free and hence either both $x_1$ and $x_2$ or both $y_1$ and $y_2$ are nonadjacent to $z_1$. By symmetry, say $x_1, x_2$. If $x_1, x_2$ have a common neighbor $x_{12}$ outside $\{u_1\}$ with $d_{G_2}(x_{12})\geq6$ or $x_1'\in N_{G_2}(x_1)$, $x_2'\in N_{G_2}(x_2)$ with $\max \{d_{G_2}(x_1'), d_{G_2(x_2')}\}\geq 5$, then (2.6) holds. If $d_{G_2}(x_1') = d_{G_2(x_2')} = 4$, then $\{x_1'u_1, x_1'u_2\}\subseteq E(G_2)$, $d_{G_2}(u_1)\geq 8$ and (2.6) holds.

If $|D_3(G_2)| = 6$, the discussion is similar to the case when $|D_3(G_2)| = 5$, then we omit it here.

Subcase 2.2. $s = 4$ and $1\leq |D_3(G_2)|\leq 8$.

Then $\kappa'_2(G_2)\geq 7$. For a vertex $v$ of degree $5$ or $6$, $G_2[N_{G_2}[v]]$ is claw-free by (2.5). Then there are at most two vertices of degree 3 in $N_{G_2}(v)$; for otherwise, there is a $K_{3, 3, 5}$ or $K_{3, 3, 6}$, contradicting Lemma 8(3).

For a vertex $w$ of degree $7$, if $\{x_1, \cdots, x_7\} = N_{G_2}(w)\subseteq D_3(G_2)$ and $\{x_1x_2, x_3x_4, x_5x_6\}\subseteq E(G_2)$, then $x_7$ has two neighbors $y_1, y_2$ such that $y_1y_2\in E(G_2)$ and $d_{G_2}(y_1)\leq d_{G_2}(y_2)$ since $G_2$ has no $P_{3, 3, 3}$. Assume that $|D_3(G_2)| = 8$. Then $d_{G_2}(y_1) = 3$, $d_{G_2}(y_2)\geq7$ and $y_1$ has a neighbor $y_3$ with $d_{G_2}(y_3)\geq 5$. If $d_{G_2}(y_3)\geq 7$ or $N_{G_2}\{x_1, \cdots, x_6\}\not\subseteq\{y_2, y_3\}$, then (2.4) holds. Otherwise, note that $5\leq d_{G_2}(y_3)\leq 6$, then $y_2y_3\in E(G_2)$ and at least 5 vertices of $\{x_1, \cdots, x_6\}$ are adjacent to $y_2$. Then $d_{G_2}(y_2)\geq8$ and (2.4) holds. Assume that $|D_3(G_2)| = 7$. If $d_{G_2}(y_1)\geq7$, then (2.4) holds. Otherwise, $G_2[N_{G_2}[y_1]]$ is claw-free and then $|N_{G_2}(y_1)\cap\{x_1, \cdots, x_7\}| = 1$ and hence there are at least two vertices $u_1, u_2\in N_{G_2}(y_1)$ with $u_1u_2\in E(G_2)$. Then there are 5 edge-disjoint triangles, a contradiction.

Thus we consider the case when $w$ has at most six neighbors of degree 3. Define a function $l(u) = \begin{cases} \frac{1}{2}, & \text{if}\; d_{G_2}(u)\geq5;\\ 0, & \text{otherwise.}\\ \end{cases}$ For a vertex $u$ of degree 3 and its neighbors $x_1, x_2, x_3$, at least two of them have degree at least 5 by the argument in Subcase 1.1. Then $l(x_1)+l(x_2)+l(x_3)\geq 1$. So

Then (2.4) holds. This completes the proof of Theorem 4.

3.   Conclusions

Note that Conjecture 3$(ii)$ is a generalization of Theorem 2 when $s\geq5$. By dealing with Conjecture 3$(i)$, we know that how the connectivity effects the $s$-hamiltonicity of claw-free graphs. By comparing them, for a 3-connected line graph $L(G)$ with $ess(L(G))\geq s$ condition other than $L(G)$ is $s$-connected, graph $G$ may have essential $l$-edge-cut for some $3\leq l\leq s$, which leads to $L(G)-X$ is disconnected for some vertex set $X\subseteq V(L(G))$ with $|X|\leq s$. There are still many properties for us to further explore.

Acknowledgments

The work is supported by the Open Project Program of Key Laboratory of Discrete Mathematics with Applications of Ministry of Education, Center for Applied Mathematics of Fujian Province, Key Laboratory of Operations Research and Cybernetics of Fujian Universities, Fuzhou University.

Conflict of interest

The author declares no conflict of interest.