Hamilton-connected properties of 3-connected {claw, hourglass, bull}-free graphs

1. Introduction

In this paper, we basically follow the most common graph-theoretical terminology and notation and for concepts not defined here we refer the reader to [1]. By a graph we always mean a simple finite undirected graph $G=(V(G),E(G))$; whenever we admit multiple edges, we always speak about a multigraph. For a set $X$, the cardinality of $X$ is denoted by $|X|$. We write $|G|$ for $|V(G)|$. For a family of graphs $\mathcal{F}$, we say that $G$ is $\mathcal{F}$-free if $G$ does not contain an induced subgraph isomorphic to a member of $\mathcal{F}$, and the graphs in $\mathcal{F}$ are referred to in this context as forbidden induced subgraphs. If $\mathcal{F}=\{F\}$, then we simply say that $G$ is $F$-free. Here, the claw is the graph $K_{1,3}$.

Several further graphs that will be used as forbidden subgraphs are shown in Figure 1 (specifically, the vertex of degree $2$ in the triangle of the bull $B_{i,j}$ will be called its mouth and denoted $\mu (B_{i,j}$)). When listing vertices of an induced subgraph $F\cong B_{i,j}$, we will always list first $\mu (F)$, and then vertices of the two paths, starting (if possible) with the shorter one. In addition, let $P_i$ and $C_i$ denote the path and cycle with $i$ vertices.

In this paper, we will consider these questions in 3-connected and claw-free graphs. A graph $G$ is hamiltonian if $G$ has a spanning cycle. The hamiltonian problem is generally considered to be determining conditions under which a graph contains a spanning cycle. To determine whether a graph is hamiltonian is very basic and popular problem. There are many results on hamiltonian properties of graphs in classes defined in terms of forbidden induced subgraphs. We first summarize some known results.

In 2002, Brousek [3] start to consider a triples of forbidden subgraphs for a graph to be Hamiltonian. Ryjáček et al. [19] and Du and Xiong [6] continue in this direction by showing that Theorem 1.1 can be substantially strengthened under an additional assumption that $G$ is ${\mathrm{\Gamma }}_0$-free, and it shows that these results of Hamiltonicity are sharp.

Theorem 1.2 adds the condition that $G$ is hourglass-free on the basis of Theorem 1.1. Ryjáček and Vrána [17] give the following result.

In 2018, Ryjáček et al. [19] start to consider a triples of forbidden subgraphs for a graph to be Hamilton-connected. Recently, Liu and Xiong [12] also considered a triples of forbidden subgraphs for a 3-connected graph to be Hamilton-connected, this result on Hamilton-connectedness are sharp.

Theorem 1.5 lists known result on pairs of forbidden subgraphs implying Hamilton-connectedness of a $3$-connected graph.

By adding the condition “${\mathrm{\Gamma }}_0$-free” to Theorem 1.5, we further prove that every 3-connected, $\{$claw, hourglass, bull$\}$-free graph is Hamilton-connected.

Proof of Theorem 1.6, consisting in direct case-distinguishing, is postponed to Section 3. In Section 2, we collect necessary known results on line graphs and on closure operations.

2. Preliminaries

In order to state results clearly, we further introduce the following notation. We denote by $N_G(v)$ (or simply $N(v)$) and $d_G(v)$ (or simply $d(v)$) the neighborhood and the degree of a vertex $v$ in $G$, respectively. For each integer $i\ge 0$, define $V_i(G)=\{v\in V(G):d(v)=i\}$. Let $N[v]=N(v)\cup \{v\}$. Let $S\subseteq V(G)$, the subgraph with $S$ as the vertex set and all the edges with both end-vertices in $S$ as the edge set is called the subgraph induced from the vertex set $S$ (or simply induced subgraph), denoted by $G[S]$. Let $S^{\prime }\subseteq E(G)$, the subgraph with $S^{\prime }$ as edge set and all the end-vertices of $S^{\prime }$ as vertex set is called the subgraph induced from edge set $S^{\prime }($or simply edge induced subgraph$)$, denoted as $G[S^{\prime }]$.

A vertex-cut (edge-cut, respectively) $X$ of a multigraph $G$ is essential if $G-X$ has at least two nontrivial components, and $G$ is essentially $k$-connected (essentially $k$-edge-connected, respectively) if every essential vertex-cut (essential edge-cut, respectively) of $H$ is of size at least $k$. Let ${\kappa }^{\prime }(G)$, $c(G)$ denote the edge connectivity and the circumference of $G$, respectively.

In Subsections 2.1-2.3, we summarize some facts that will be need in our proof of Theorem 1.6.

2.1. Line graphs of multigraphs and their preimages

The line graph of a given $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$. The induced sub(multi)graph on a set $M\subset V(G)$, denoted by $G[M]$.

The multigraph $H$ will be called the preimage of a line graph $G$ and denoted $H=L^{-1}(G)$. We will also use the notation $a=L(e)$ and $e=L^{-1}(a)$ for an edge $e\in E(H)$ and the corresponding vertex $a\in V(G)$.

A vertex $x\in V(G)$ is eligible if $G[N(x)]$ is a connected noncomplete graph, and we use $V_{EL}(G)$ to denote the set of all eligible vertices of $G$. The local completion of $G$ at a vertex $x$ is the graph $G_x^{\ast }$ obtained from $G$ by adding all edges with both vertices in $N(x)$ (note that the local completion at $x$ turns $x$ into a simplicial vertex, and preserves the $K_{1,3}$-free property of $G$). The closure $cl(G)$ of a $K_{1,3}$-free graph $G$ was defined as the graph obtained from $G$ by recursively performing the local completion operation at eligible vertices, as long as this is possible(more precisely: $cl(G)=G_k$, where $G_1,\dots ,G_k$ is a sequence of graphs such that $G_1=G$, $G_{i+1}=(G_i{)}_x^{\ast }$ for some $x\in V_{EL}(G_i),i\in 1,\dots ,k-1$, and $V_{EL}(G_k)=\mathrm{\varnothing }$). We say that $G$ is closed if $G=cl(G)$. The closure $cl(G)$ of a $K_{1,3}$-free graph $G$ is uniquely determined, is the line graph of a triangle-free graph, and is Hamiltonian if and only if so is $G$. However, as observed in [2], the closure operation does not preserve (non-)Hamilton-connectedness of $G$. It is a well-known fact that

We recall that if $G=L(H)$, then a graph $F$ is an induced subgraph of $G$ if and only if $L^{-1}(F)$ is a subgraph (not necessarily induced) of $H$.

The core of $H$ is the multigraph $H_0$ obtained from $H$ by deleting all the vertices of degree 1, and replacing the path $xyz$ by the edge $xz$ for each $y$ of degree 2, and denoted $co(H)$.

Obviously, if $G$ is $K_{1,3}$-free, then so is $G_x^{\ast }$. Note that in the special case when $G$ is a line graph and $H=L^{-1}(G)$, $G_x^{\ast }$ is the line graph of the graph obtained from $H$ by contracting the edge $L^{-1}(x)$ into a vertex and replacing the created loop(s) by pendant edge(s). The following results show some properties of eligible vertexs.

The following theorem was proved in [4], [5].

A multigraph $H$ is strongly spanning trailable if for any edge $e_1,e_2\in E(H)$ (possibly $e_1=e_2$), the multigraph $H(e_1,e_2)$, which is obtained from $H$ by replacing the edge $e_1$ by a path $u_1{v}_{e_1}{v}_1$ and the edge $e_2$ by a path $u_2{v}_{e_2}{v}_2$, has a spanning $(v_{e_1},v_{e_2})$-trail. The following theorem establishes a correspondence between a $IDT$ in $H$ and a hamiltonian path in $L(H)$.

${\mathcal{W}}_0$ is the family of multigraphs obtained from the Wagner graph $W_8$ by subdividing one of its edges and adding at least one edge between the new vertex and exactly one of its neighbors (see Figure 2).

2.2. $SM$-closure

For a given $K_{1,3}$-free graph $G$, a graph $G^M$, as introduced in [9], is defined by the following construction.

1. If $G$ is Hamilton-connected, we set $G^M=cl(G)$.

2. If $G$ is not Hamilton-connected, we recursively perform the local completion operation at such eligible vertices for which the resulting graph is still not Hamilton-connected, as long as this is possible. We obtain a sequence of graphs $G_1$, …, $G_k$ such that

   • $G_1=G$,

   • $G_{i+1}=(G_i{)}_{x_i}^{\ast }$ for some $x_i\in V_{EL}(G_i)$, $i=1,\dots ,k-1$,

   • $G_k$ has no hamiltonian $(a,b)$-path for some $a,b\in V(G_k)$,

   • for any $x\in V_{EL}(G_k)$, $(G_k{)}_x^{\ast }$ is Hamilton-connected,

and set $G^M=G_k$.

A resulting $G^M$ is called a strong $M$-closure (or briefly an $SM$-closure) of the graph $G$, and a graph $G$ equal to its $SM$-closure is said to be $SM$-closed. Note that for a given graph $G$, its $SM$-closure is not uniquely determined. As shown in [15] and [9], if $G$ is $SM$-closed, then $G=L(H)$, where $H$ does not contain a subgraph$($not necessarily induced$)$ isomorphic to any of the graphs in Figure 3.

For $x,y\in V(G)$, a path (trail) with endvertices $x,y$ is referred to as an $(x,y)$-path ($(x,y)$-trail), a trail with terminal edges $e,f\in E(G)$ is called an $(e,f)$-trail, and Int$(T)$ denotes the set of interior vertices of a trail $T$. A set of vertices $M\subset V(G)$ dominates an edge $e$, if $e$ has at least one vertex in $M$, and a subgraph $F\subset G$ dominates $e$ if $V(F)$ dominates $e$. A closed trail $T$ is a dominating closed trail (abbreviated DCT) if $T$ dominates all edges of $G$, and an $(e,f)$-trail is an internally dominating $(e,f)$-trail (abbreviated $(e,f)$-IDT) if Int$(T)$ dominates all edges of $G$.

The following results show some properties of the $SM$-closure.

We will also need the following lemma on $SM$-closed graphs proved in [16].

2.3. Closure operations and bull-free graphs

The concept of $SM$-closure can be further strengthened by omitting the eligibility assumption in the local completion operation. Specifically, for a given $K_{1,3}$-free graph $G$, Liu et al. [11] constructed a graph $G^U$ by the following construction.

1. If $G$ is Hamilton-connected, we set $G^U=K_{|V(G)|}$.

2. If $G$ is not Hamilton-connected, we recursively perform the local completion operation at such vertices for which the resulting graph is still not Hamilton-connected, as long as this is possible. We obtain a sequence of graphs $G_1$, $\dots$, $G_k$ such that

   • $G_1=G$,

   • $G_{i+1}=(G_i{)}_{x_i}^{\ast }$ for some $x_i\in V(G_i)$, $i=1,\dots ,k-1$,

   • $G_k$ has no hamiltonian $(a,b)$-path for some $a,b\in V(G_k)$,

   • for any $x\in V(G_k)$, $(G_k{)}_x^{\ast }$ is Hamilton-connected,

and set $G^M=G_k$.

A resulting $G^U$ is called a ultimate $M$-closure (or briefly an $UM$-closure) of the graph $G$, and a graph $G$ equal to its $UM$-closure is said to be $UM$-closed. When applying closure techniques to $\{claw,{\mathrm{\Gamma }}_0,bull\}$-free graphs, the main problem is that a closure of a $\{K_{1,3},{\mathrm{\Gamma }}_0,B_{i,j}\}$-free graph is not necessarily $\{K_{1,3},{\mathrm{\Gamma }}_0,B_{i,j}\}$-free (i.e., in the terminology of [14], the class of $\{K_{1,3},{\mathrm{\Gamma }}_0,B_{i,j}\}$-free graphs is not stable under the closure operation). Unfortunately, this is the case with all the closure operations mentioned in the previous subsections.

We say that a vertex $x\in V(G)$ is simplicial if the subgraph induced by $G[N(x)]$ is complete graph, and we use $V_{SI}(G)$ to denote the set of all simplicial vertices of $G$.

It turns out that this difficulty can be overcome by working in a slightly larger class of graphs which contains all the requested $\{K_{1,3},{\mathrm{\Gamma }}_0,B_{i,j}\}$-free graphs but is stable under the closure. Ryjáček and Vrána [18] defined the class ${\mathcal{B}}_{i,j}$ as follows, and they proved the following properties.

• For any positive integers $i,j$, ${\mathcal{B}}_{i,j}$ is the class of all $K_{1,3}$-free graphs $G$ such that every induced subgraph $F\subset G$, $F\simeq {\mathcal{B}}_{i,j}$, satisfies $\mu (F)\in V_{SI}(G)$.

Clearly, every $\{K_{1,3},B_{i,j}\}$-free graph is in ${\mathcal{B}}_{i,j}$.

3. Proof of Theorem 1.6

We will always write the list such that integers $1\le i\le j$ and $i+j=7$, we use $S_{1,2i+1,2j+1}$ to denote the graph obtained from $K_{1,3}$ by subdividing two of its edges $2i$ and $2j$ times, respectively, where the labeling of vertices as in Figure 4, and the vertex $o$ will be called the center vertex. It is easy to observe that $L^{-1}({\mathrm{\Gamma }}_0)$ is the unique graph with degree sequence $3,3,1,1,1,1$ and $L^{-1}(B_{2i,2j})=S_{1,2i+1,2j+1}$. We will use the notation $S_{1,i,j}(o,a_1,b_1{b}_2\dots b_i,c_1\dots c_j)(S_{1,i,j}\subseteq S(o,a_1,b_1{b}_2\dots b_{i^{\prime }},c_1\dots c_{j^{\prime }})$ with integers $i^{\prime }\ge i$ and $j^{\prime }\ge j)$ to denote the subgraph $S_{1,i,j}$. Now, we present the proof of Theorem 1.6.

Proof of Theorem 1.6. Let $G$ be a 3-connected $\{K_{1,3},{\mathrm{\Gamma }}_0,X\}$-free graph, where $X\in \{B_{2,12}$, $B_{4,10}$,  $B_{6,8}\}$, and suppose, to the contrary, that $G$ is not Hamilton-connected. By Theorems 2.3 and 2.11, we can assume that $G$ is $UM$-closed and $G\in {\mathcal{B}}_{2,12}\cup {\mathcal{B}}_{4,10}\cup {\mathcal{B}}_{6,8}$. Obviously, $G$ is also $SM$-closed, implying that $G$ is a line graph and $H=L^{-1}(G)$ has special structure (contains no diamond, no multitriangle and triple edge), and let $H_0$ be the core of $H$. By Theorem 2.6 (4), $H_0$ is not strongly spanning trailable. By Lemma 2.2, every induced hourglass in $G$ is centered at an eligible vertex. By Theorem 2.7, $H$ has at most two triangles or an multiedge. Hence, we may let $$\begin{array}{r}{E}_0\text{be~the~edge~set~of~two~triangles~or~the~multiedge~in}H.\end{array}$$ By Theorem 2.6 (1), $$\begin{array}{r}{\kappa }^{\prime }(H_0)\ge 3.\end{array}\text{tg}1$$ For any edge $e\in E(H_0)\mathrm{\setminus }{E}_0$, $L(e)$ is not an eligible vertex in $G$ by Lemma 2.9, i.e., the edge $e$ cannot be a central edge of an $L^{-1}({\mathrm{\Gamma }}_0)$ for some induced hourglass ${\mathrm{\Gamma }}_0$ of $G$. Thus we have $$\begin{array}{}\text{(2)}& \begin{array}{r}\text{each~edge~of}E(H_0)\mathrm{\setminus }{E}_0\text{should~be~subdivided~by~a~vertex~of~degree}2\text{in}H.\end{array}\end{array}$$ It suffices to show that $H$ contains all possible subgraphs $S_{1,2i+1,2j+1}\in \{S_{1,3,13}$, $S_{1,5,11}$, $S_{1,7,9}\}$, where positive integers $i+j=7$.

Therefore $c(H_0)\ge 9$ and $|V(H_0)|\ge 10$. Throughout the proof, we use the following notation:

• $C_{c(H_0)}=v_1{v}_2\dots v_{c(H_0)}{v}_1$ always denotes a longest cycle of $H_0$, and $C=P{I}_H(C_{c(H_0)})$;

• Set $m^{H_0}=|E_0\cap E(C_{c(H_0)})|$;

• Set ${\mathcal{D}}_{H_0}=V(H_0)\setminus V(C_{c(H_0)})$;

• Let $E_{H_0}^1$ be the set of all edges between $C_{c(H_0)}$ and ${\mathcal{D}}_{H_0}$. Then $|E_{H_0}^1|\ge 3$;

By (2), $C_{c(H_0)}$ has at least $c(H_0)-m^{H_0}$ edges that should be subdivided by $c(H_0)-m^{H_0}$ vertices of degree $2$ in $H_0$, then $|V(C)|=2c(H_0)-m^{H_0}$. For integers $1\le r<s\le c(H_0)$, we use $v_{r,s}$ to denote the vertex subdivide edge $v_r{v}_s$ in $C_{c(H_0)}$. An edge $v_r{v}_s\in E(C_{c(H_0)})$ is a $l$-chord if the shortest one of the two subpaths of $C_{c(H_0)}$ determined by $v_r$ and $v_s$ has $l$ internal vertices.

By Claims 3.3 and 3.4, we can get that $H_0$ is simple graph.

By Claims 3.4 and 3.5, $H_0$ contains at least one triangle.

If $m^{H_0}=2$, then $H_0$ has exactly one triangle and $C_{c(H_0)}$ contains exactly three vertices of the triangle, where the vertices of the triangle are pairwise adjacent in $H_0$. Without loss of generally, we denote the triangle by $v_1{v}_2{v}_3{v}_1$. Choose a shortest path $P^{r,s}\subseteq H[E({\mathcal{D}}_{H_0})\cup E_{H_0}^1]$ with two vertices $v_r,v_s\in V(C_{c(H_0)})$ as its end-vertices, respectively, where the edges incident with vertices $v_r$ and $v_s$ in $P^{r,s}$ are denoted by $e_{r,s}^r$ and $e_{r,s}^s$, respectively. For edge $e_{r,s}^r,e_{r,s}^s\notin E_0$ and $e_{r,s}^r,e_{r,s}^s\in E_{H_0}^1$, by (2), they should be subdivided by two vertices of degree $2$ in $H$, say $x_{r,s}^r,x_{r,s}^s\in V(H)$, respectively. Let ${\mathcal{P}}^{\prime }$ be the set of all path $P^{r,s}$ satisfying integer $1\le r,s\le c(H_0)$.