1 Introduction
We consider finite simple graphs and follow the books [Reference Bondy and Murty3, Reference West12] for terminology and notation. The order of a graph is its number of vertices. Given a graph G, we denote by
$V(G)$
and
$E(G)$
the vertex set and edge set of G. Denote by
$N_{G}(v)$
the neighbourhood in G of a vertex
$v.$
The join of graphs G and H, denoted by
$G\vee H$
, is the graph obtained from the disjoint union
$G+H$
by adding edges to join every vertex in G and every vertex in
$H.$
For an edge e of
$G,$
the graph
$G/e$
is obtained by contracting the edge e in
$G.$
A wheel is a graph formed by a cycle (called the rim) joining a new vertex (called the centre). An i-wheel is a wheel such that its rim has i vertices. A hole in a graph is an induced cycle of length at least
$4.$
For an integer
$\ell \ge 4$
, a graph is
$\ell $
-holed if all its holes have length exactly
$\ell .$
Thomassen’s famous chord conjecture from 1976 is as follows [Reference Alspach and Godsil1, Reference Thomassen9].
Conjecture 1.1 (Thomassen, 1976).
Every longest cycle in a
$3$
-connected graph has a chord.
Although this beautiful conjecture remains unsolved, there are many partial results where Conjecture 1.1 has been proved (see [Reference Birmelé2, Reference Kawarabayashi, Niu and Zhang6–Reference Li and Zhang8, Reference Thomassen10, Reference Thomassen11, Reference Wu, Broersma and Kang13, Reference Zhang14]).
Definition 1.2. The circumference of a graph G, denoted by
$c(G)$
, is the length of its longest cycles. The induced circumference of a graph G, denoted by
$c'(G)$
, is the length of its longest induced cycles.
It is obvious that
$c'(G)\leq c(G)$
. We denote by
$\delta (G)$
the minimum degree of the graph
$G.$
In [Reference Harvey5], Harvey posed the following conjecture.
Conjecture 1.3 (Harvey, 2017).
Let
$k\ge 1$
be an integer. If G is a
$2$
-connected graph with
$\delta (G)\ge \lceil k/2+2\rceil $
, then
$c'(G)\leq c(G)-k$
.
We observe that the wheel is a unique Hamiltonian graph for which the circumference and the induced circumference differ by exactly one. Thus, we only need to consider whether Harvey’s conjecture holds for non-Hamiltonian graphs. Based on this, we make a slight modification to Conjecture 1.3 when
$k=2$
.
Conjecture 1.4. If G is a non-Hamiltonian
$2$
-connected graph with
$\delta (G)\ge 3$
, then
$c'(G)\leq c(G)-2$
.
We pose the following conjecture which is equivalent to Conjecture 1.4.
Conjecture 1.5. Let G be a
$2$
-connected graph with
$\delta (G)\kern1.3pt{\geq}\kern1.3pt 3$
. Then,
${c(G)\kern1.4pt{=}\kern1.4pt c'(G)\kern1.4pt{+}\kern1.4pt1}$
if and only if G is a wheel.
In Section 2, we prove that Conjectures 1.4 and 1.5 are equivalent. In Section 3, we prove that Conjecture 1.4 holds for
$\ell $
-holed graphs and graphs with a small induced circumference.
2 Equivalence of Conjectures 1.4 and 1.5
Proof that Conjectures 1.4 and 1.5 are equivalent.
Suppose that Conjecture 1.4 holds. Let G be a
$2$
-connected graph of order n with
$\delta (G)\geq 3$
. If G is a wheel, then
$c(G)=c'(G)+1$
by the definition of a wheel. If
$c(G)=c'(G)+1$
, by Conjecture 1.4, G is Hamiltonian. Thus,
$c(G)=n$
and
$c'(G)=n-1$
. Let C be a longest induced cycle of G. Without loss of generality, assume that
$V(G)\setminus V(C)=\{u\}$
. Since
$\delta (G)\geq 3$
, this implies that
$G=C\vee u$
. That is, G is a wheel.
Conversely, suppose that Conjecture 1.5 holds. To prove Conjecture 1.4, let G be a counterexample to Conjecture 1.4 with minimum order. Then,
$c(G)\leq c'(G)+1$
. Since
$c'(G)\leq c(G)$
, this implies that
$$ \begin{align*} c'(G)\leq c(G)\leq c'(G)+1. \end{align*} $$
If
$c(G)=c'(G)+1$
, Conjecture 1.5 implies that G is a wheel, that is, G is Hamiltonian, which is a contradiction. Thus,
$c(G)=c'(G)$
.
Let C be a longest chordless cycle of G. For convenience, we may assume that
$c(G)=k$
and
$C=v_1,v_2,\ldots ,v_k,v_1$
.
Claim 2.1.
$k\geq 4$
.
Proof. Otherwise, suppose
$k\leq 3$
. This implies that C is a triangle. Let H be a component of
$G-C$
. Since G is
$2$
-connected,
$|N_C(H)|\geq 2$
. This implies that
$C\cup H$
contains a cycle with length at least
$4$
, which is a contradiction.
By Claim 2.1, since C is a longest cycle,
$N_G(v_i)\cap N_G(v_{i+1})=\emptyset $
. Let
$G'=G/v_1v_2$
and denote the new vertex by
$v^*$
. Since
$N_G(v_1)\cap N_G(v_2)=\emptyset $
and
$\delta (G)\geq 3$
, we have
$\delta (G')\geq 3$
.
Claim 2.2.
$G'$
is non-Hamiltonian.
Proof. Otherwise, suppose
$G'$
is Hamiltonian. Let
$C'$
be a Hamiltonian cycle in
$G'$
. Clearly,
$C'$
can be transformed to a cycle in G. We denote this cycle in G by
$C_1$
. It is obvious that the cycle
$C_1$
in G is at least as long as the cycle
$C'$
in
$G'$
. Since G is non-Hamiltonian and
$G'$
is Hamiltonian,
$c(G')=n-1=c(G)$
. This implies that
$c'(G)=n-1$
, that is,
$k=n-1$
. Let
$V(G)\setminus V(C)=\{u\}$
. Thus,
$G=C\vee u$
and it follows that G is Hamiltonian, which is a contradiction.
Claim 2.3.
$G'$
is
$2$
-connected.
Proof. If
$G'$
has a cut vertex u, then we assert that
$u=v^*.$
Otherwise, u is a cut vertex of
$G,$
which is a contradiction. It follows that
$\{v_1,v_2\}$
is a vertex cut in G. Let H be a component in
$G-\{v_1,v_2\}$
that contains no vertex of
$V(C)\setminus \{v_1,v_2\}$
. Since G is
$2$
-connected,
$\{v_1,v_2\}\subseteq N_G(H)$
. This implies that C can be transformed into a cycle
$C^*$
in G by adding a path in H and
$C^*$
is strictly longer than C, which is a contradiction.
Note that
$G'$
is a non-Hamiltonian
$2$
-connected graph of order
$n-1$
with
${\delta (G')\geq 3}$
. Therefore,
$c(G')\geq c'(G')+2$
. However,
$C/v_1v_2$
is an induced cycle in
$G'$
. Thus,
$c'(G')\geq k-1$
. This implies that
$c(G')\geq k+1$
. Let
$C^{\prime \prime }$
be a longest cycle in
$G'$
. Clearly,
$C^{\prime \prime }$
can be transformed to a cycle in G. We denote this cycle in G by
$C_1^{\prime \prime }$
. It is obvious that the cycle
$C_1^{\prime \prime }$
in G is at least as long as the cycle
$C^{\prime \prime }$
in
$G'$
. This implies that
$c(G)\geq k+1$
, which contradicts
$c(G)=c'(G)=k$
. This proves Conjecture 1.4.
3 Graphs with a small induced circumference and
$\ell $
-holed graphs
Let G be a graph. We denote by
$d_G(u, v)$
the distance between two vertices u and v in G. Let S be a set of vertices and let u be a vertex. We define
$$ \begin{align*}d(u,S)=\min\{ d(u,v) : v\in S\}.\end{align*} $$
Let
$X,Y\subseteq V(G)$
. An
$(X,Y)$
-path is a path with one endpoint in X, the other endpoint in Y and internal vertices not in
$X\cup Y$
. If
$X=\{x\}$
, then we use
$(x,Y)$
-path instead of
$(\{x\}, Y)$
-path.
Theorem 3.1. Let G be a
$2$
-connected non-Hamiltonian graph with
$\delta (G)\geq 3$
. If
$c'(G)\leq 6$
, then
$c(G)\geq c'(G)+2$
.
Proof. It suffices to show that G has a cycle with length at least
$c'(G)+2$
. Here, we only prove this for the case of
$c'(G)=6$
. The other three cases (for
$c'(G)=3,4,5$
) can be proved by a similar analysis and we omit the proofs.
Let G be a
$2$
-connected non-Hamiltonian graph with
$\delta (G)\geq 3$
and
$c'(G)=6$
. Suppose G is a counterexample of Theorem 3.1, that is,
$c'(G)\leq c(G)\leq c'(G)+1$
. Let
$C=v_1,v_2,\ldots ,v_6,v_1$
be a chordless cycle in G. Let
$L_i=\{u\in V(G):d(u, V(C))=i\}$
for any positive integer i.
Claim 3.1.
$L_2=\emptyset $
.
Proof. Otherwise, let
$u\in L_2$
. Suppose that u has a neighbour
$u'$
in
$L_2$
. Since G is
$2$
-connected, there exist two
$(\{u,u'\}, V(C))$
-paths
$P_1,P_2$
such that
$V(P_1)\cap V(P_2)=\emptyset $
. For convenience, assume that
$P_1=u,a_1,\ldots ,v_1$
and
$P_2=u',b_1,\ldots ,v_i$
. Note that
$P_1,u,u',P_2$
is a path with length at least
$5$
. It follows that either
$u,P_1,v_1,v_2,\ldots , v_i,P_2,u',u$
is a cycle with length at least
$8$
or
$u',P_2,v_i,v_{i+1},\ldots ,v_6,v_1$
,
$P_1,u,u'$
is a cycle with length at least
$8$
, which is a contradiction. Hence,
$N(u)\subseteq L_1$
. Since G is
$2$
-connected, there exist two
$(u, V(C))$
-paths
$P_3,P_4$
such that
$V(P_3)\cap V(P_4)=\{u\}$
. Without loss of generality, we may assume that
$P_3=u,c_1,\ldots ,c_s,v_1$
and
$P_4=u,d_1,\ldots ,d_t,v_i$
, respectively. To forbid
$u,P_3,v_1,v_2\ldots , v_i,P_4,u$
and
$u,P_4,v_i,v_{i+1}\ldots , v_6,v_1,P_3,u$
from being a cycle of length greater than
$7$
, we must have
$v_i=v_4$
and
$s=t=1$
. Since
$c'(G)=6$
, the cycle
$u,c_1,v_1,v_2,v_3,v_4,d_1,u$
has a chord. Clearly,
$N_G(\{c_1,d_1\})\cap \{v_2,v_3\}=\emptyset .$
This implies that
$c_1d_1\in E(G)$
. Since
$\delta (G)\geq 3$
, u has a neighbour
$u^*$
distinct from
$c_1$
and
$d_1$
. It is obvious that
$N_G(u^*)\cap \{c_1,d_1\}=\emptyset $
. Since
$u^*\in L_1$
, it follows that
$u^*$
has a neighbour in
$V(C)$
, say
$v_j$
. If
$j\notin \{v_1,v_4\}$
, then either
$u,c_1,v_1,v_2,\ldots ,v_j,u^*,u$
is a cycle with length at least
$8$
or
$u,u^*,v_j,v_{j+1},\ldots ,v_6,v_1,c_1,u$
is a cycle with length at least
$8$
, which is a contradiction. By symmetry, we may assume that
$v_j=v_1$
. However, it follows that
$u,c_1,d_1,v_4,v_5,v_6,v_1,u^*,u$
is a cycle with length at least
$8$
, which is a contradiction.
By Claim 3.1,
$V(C)$
is a dominating set of
$G.$
Let
$H_1,\ldots , H_t$
be the components of
$G-V(C)$
. We will discuss two cases.
Case 3.1. There exists a component
$H_i$
such that
$N_C(H_i)$
has two consecutive vertices in C.
Without loss of generality, assume
$i=1$
and
$\{v_1,v_2\}\subseteq N_C(H_1)$
. Suppose that
$N_C(H_1)=\{v_1,v_2\}$
. As G is
$2$
-connected and
$\delta (G)\ge 3$
, there exist two distinct vertices
$v_1'$
and
$v_2'$
such that
$v_1'\in N_{H_1}(v_1)$
and
$v_2'\in N_{H_1}(v_2)$
. Let
$P_{v_1'v_2'}$
be a
$(v_1',v_2')$
-path with interior in
$H_1$
. Then,
$v_1,v_1',P_{v_1'v_2'},v_2',v_2,v_3,v_4,v_5,v_6,v_1$
is a cycle with length at least
$8$
, which is a contradiction. Therefore,
$\{v_3,v_4\}\cap N_C(H_1)\neq \emptyset $
or
$\{v_5,v_6\}\cap N_C(H_1)\neq \emptyset $
. By symmetry, we assume that
$\{v_3,v_4\}\cap N_C(H_1)\neq \emptyset $
.
Subcase 3.1.1.
$\{v_3,v_4\}\subseteq N_C(H_1)$
.
Suppose that
$\{v_5,v_6\}\subseteq N_C(H_1)$
. We claim that
$N_{H_1}(C)$
is a single vertex. Otherwise, for some
$i\in [6]$
, there exists a
$(v_i,v_{i+1})$
-path
$P_{v_i,v_{i+1}}$
with length at least
$3$
and interior in
$V(H_1)$
, and hence
$v_i,P_{v_i,v_{i+1}},v_{i+1},\ldots ,v_i$
is a cycle with length at least
$8$
, which is a contradiction. Hence, G contains a subgraph W isomorphic to a
$6$
-wheel. As G is non-Hamiltonian,
$V(G)\setminus V(W)\neq \emptyset $
. Let
$v\in V(G)\setminus V(W)$
. Since G is
$2$
-connected, there exist two
$(v,V(W))$
-paths
$Q_1,Q_2$
such that
$V(Q_1)\cap V(Q_2)= \emptyset $
. It is not hard to find a cycle with length at least
$8$
in
$V(W)\cup V(Q_1)\cup V(Q_2)$
, which is a contradiction. Therefore, we have
$v_5\notin N_C(H_1)$
or
$v_6\notin N_C(H_1)$
. By symmetry, we assume that
${v_5\notin N_C(H_1)}$
. Without loss of generality, we assume that
$v_5\in N_C(H_2)$
.
Suppose that
$v_4\in N_C(H_2)$
. Let
$P_{v_4,v_5}$
be a
$(v_4,v_5)$
-path with interior in
$V(H_2)$
and let
$P_{v_1,v_2}$
be a
$(v_1,v_2)$
-path with interior in
$V(H_1)$
. Then,
$v_4,P_{v_4,v_5},v_5,v_6,v_1,P_{v_1,v_2},v_2,v_3,v_4$
is a cycle with length at least
$8$
, which is a contradiction. Suppose that
$v_3\in N_C(H_2)$
. Let
$P_{v_5,v_3}$
be a
$(v_5,v_3)$
-path with interior in
$V(H_2)$
and let
$P_{v_4,v_2}$
be a
$(v_4,v_2)$
-path with interior in
$V(H_1)$
. Then,
$v_5,P_{v_5,v_3},v_3,v_4,P_{v_4,v_2},v_2,v_1,v_6,v_5$
is a cycle with length at least
$8$
, which is a contradiction. By similar analysis, we also have
$v_6,v_2\notin N_C(H_2)$
. Since G is
$2$
-connected,
$N_C(H_2)=\{v_5,v_1\}$
. Furthermore, there exists a
$(v_1,v_5)$
-path
$P_{v_1,v_5}$
with length at least
$3$
and interior in
$V(H_2)$
. Let
$P_{v_2,v_1}$
be a
$(v_2,v_1)$
-path with interior in
$V(H_1)$
. Then,
$v_1,P_{v_1,v_5},v_5,v_4,v_3,v_2,P_{v_2,v_1},v_1$
is a cycle with length at least
$8$
, which is a contradiction.
Subcase 3.1.2.
$v_3\in N_C(H_1)$
and
$v_4\notin N_C(H_1)$
.
Without loss of generality, we assume that
$v_4\in N_C(H_2)$
. Suppose that
$v_2\in N_C(H_2)$
. Let
$P_{v_4,v_2}$
be a
$(v_4,v_2)$
-path with interior in
$V(H_2)$
and let
$P_{v_3,v_1}$
be a
$(v_3,v_1)$
-path with interior in
$V(H_1)$
. Then,
$v_4,P_{v_4,v_2},v_2,v_3,P_{v_3,v_1},v_1,v_6,v_5,v_4$
is a cycle with length at least
$8$
, which is a contradiction. Suppose that
$v_3\in N_C(H_2)$
. Let
$P_{v_4,v_3}$
be a
$(v_4,v_3)$
-path with interior in
$V(H_2)$
and let
$P_{v_3,v_2}$
be a
$(v_3,v_2)$
-path with interior in
$V(H_1)$
. Then,
$v_4,P_{v_4,v_3},v_3,P_{v_3,v_2},v_2,v_1,v_6,v_5,v_4$
is a cycle with length at least
$8$
, which is a contradiction. By a similar analysis,
$v_5\notin N_C(H_2)$
. Furthermore, we have
$\{v_1,v_6\} \not \subset N_C(H_2)$
.
Suppose that
$v_6\in N_C(H_2)$
. Then there exists a
$(v_6,v_4)$
-path
$P_{v_6,v_4}$
with length at least
$3$
and interior in
$V(H_2)$
. Let
$P_{v_2,v_1}$
be a
$(v_2,v_1)$
-path with interior in
$V(H_1)$
. Then,
$v_6,P_{v_6,v_4},v_4,v_3,v_2,P_{v_2,v_1},v_1,v_6$
is a cycle with length at least
$8$
, which is a contradiction. Therefore,
$N_C(H_2)=\{v_4,v_1\}$
.
Suppose that
$v_6\in N_C(H_1)$
. Let
$P_{v_6,v_3}$
be a
$(v_6,v_3)$
-path with interior in
$V(H_1)$
and let
$P_{v_1,v_4}$
be a
$(v_1,v_4)$
-path with interior in
$V(H_2)$
. Then,
$v_6,P_{v_6,v_3},v_3,v_2,v_1,P_{v_1,v_4},v_4,v_5,v_6$
is a cycle with length at least
$8$
, which is a contradiction. Without loss of generality, we may assume that
$v_6\in N_C(H_3)$
.
Suppose that
$v_1\in N_C(H_3)$
. Let
$P_{v_6,v_1}$
be a
$(v_6,v_1)$
-path with interior in
$V(H_3)$
and let
$P_{v_1,v_2}$
be a
$(v_1,v_2)$
-path with interior in
$V(H_1)$
. Then,
$v_6,P_{v_6,v_1},v_1,P_{v_1,v_2},v_2,v_3,v_4,v_5,v_6$
is a cycle with length at least
$8$
, which is a contradiction. Similarly, we have
$v_5\notin N_C(H_3)$
. Suppose that
$v_2\in N_C(H_3)$
. Let
$P_{v_6,v_2}$
be a
$(v_6,v_2)$
-path with interior in
$V(H_3)$
and let
$P_{v_1,v_3}$
be a
$(v_1,v_3)$
-path with interior in
$V(H_1)$
. Then,
$v_6,P_{v_6,v_2},v_2,v_1,P_{v_1,v_3},v_3,v_4,v_5,v_6$
is a cycle with length at least
$8$
, which is a contradiction. Suppose that
$v_3\in N_C(H_3)$
. Let
$P_{v_6,v_3}$
be a
$(v_6,v_3)$
-path with interior in
$V(H_3)$
and let
$P_{v_1,v_4}$
be a
$(v_1,v_4)$
-path with interior in
$V(H_2)$
. Then,
$v_6,P_{v_6,v_3},v_3,v_2,v_1,P_{v_1,v_4},v_4,v_5,v_6$
is a cycle with length at least
$8$
, which is a contradiction. Therefore,
$N_C(H_3)=\{v_6,v_4\}$
. Then, there exists a
$(v_6,v_4)$
-path
$P_{v_6,v_4}$
with length at least
$3$
and its interior in
$V(H_3)$
. Let
$P_{v_3,v_2}$
be a
$(v_1,v_2)$
-path with interior in
$V(H_1)$
. Then,
$v_6,P_{v_6,v_4},v_4,v_3,P_{v_3,v_2},v_2,v_1,v_6$
is a cycle with length at least
$8$
, which is a contradiction.
Subcase 3.1.3.
$v_4\in N_C(H_1)$
and
$v_3\notin N_C(H_1)$
.
Without loss of generality, we may assume that
$v_3\in N_C(H_2)$
. Suppose that
${v_4\in N_C(H_2)}$
. Let
$P_{v_3,v_4}$
be a
$(v_3,v_4)$
-path with interior in
$V(H_2)$
and let
$P_{v_1,v_2}$
be a
$(v_1,v_2)$
-path with interior in
$V(H_1)$
. Then,
$v_1,P_{v_1,v_2},v_2,v_3,P_{v_3,v_4},v_4,v_5,v_6,v_1$
is a cycle with length at least
$8$
, which is a contradiction. Similarly,
$v_2\notin N_C(H_2)$
. Suppose that
$v_1\in N_C(H_2)$
. Let
$P_{v_3,v_1}$
be a
$(v_3,v_1)$
-path with interior in
$V(H_2)$
and let
$P_{v_2,v_4}$
be a
$(v_2,v_4)$
-path with interior in
$V(H_1)$
. Then,
$v_3,P_{v_3,v_1},v_1,v_6,v_5,v_4,P_{v_4,v_2},v_2,v_3$
is a cycle with length at least
$8$
, which is a contradiction. Suppose that
$v_5\in N_C(H_2)$
. Let
$P_{v_5,v_3}$
be a
$(v_5,v_3)$
-path with interior in
$V(H_2)$
and let
$P_{v_2,v_4}$
be a
$(v_2,v_4)$
-path with interior in
$V(H_1)$
. Then,
$v_3,P_{v_3,v_5},v_5,v_6,v_1,v_2,P_{v_2,v_4},v_4$
is a cycle with length at least
$8$
, which is a contradiction. Therefore,
$N_C(H_2)=\{v_3,v_6\}$
. Furthermore, there exists a
$(v_3,v_6)$
-path
$P_{v_3,v_6}$
with length at least
$3$
and interior in
$V(H_2)$
. Let
$P_{v_2,v_4}$
be a
$(v_2,v_4)$
-path with interior in
$V(H_1)$
. Then,
$v_3,P_{v_3,v_6},v_6,v_1,v_2,P_{v_2,v_4},v_4,v_3$
is a cycle with length at least
$8$
, which is a contradiction.
Case 3.2. For each component
$H_i$
of
$G-V(C)$
,
$N_C(H_i)$
is independent in C.
Subcase 3.2.1. There exists a component
$H_i$
such that
$d_C(x,y)=2$
for some
${x,y\in N_C(H_i)}$
.
Without loss of generality, we may assume that
$\{v_1,v_3\}\subseteq N_C(H_1)$
and
$v_2\in N_C(H_2)$
. Suppose that
$v_4\in N_C(H_2)$
. Let
$P_{v_2,v_4}$
be a
$(v_2,v_4)$
-path with interior in
$V(H_2)$
and let
$P_{v_1,v_3}$
be a
$(v_1,v_3)$
-path with interior in
$V(H_1)$
. Then,
$v_1,P_{v_1,v_3},v_3,v_2,P_{v_2,v_4},v_4,v_5,v_6,v_1$
is a cycle with length at least
$8$
, which is a contradiction. Similarly, we have
${v_6\notin N_C(H_2)}$
. Therefore, we have
$N_C(H_2)=\{v_2,v_5\}$
. Furthermore, there exists a
$(v_2,v_5)$
-path
$P_{v_2,v_5}$
with length at least
$3$
and its interior in
$V(H_2)$
. Let
$P_{v_3,v_1}$
be a
$(v_3,v_1)$
-path with interior in
$V(H_1)$
. Then,
$v_2,P_{v_2,v_5},v_5,v_4,v_3,P_{v_3,v_1},v_1,v_2$
is a cycle with length at least
$8$
, which is a contradiction.
Subcase 3.2.2. For any
$x,y\in N_C(H_i)$
,
$d_C(x,y)=3$
.
Without loss of generality, we may assume that
$v_1\in N_C(H_1)$
and
$v_2\in N_C(H_2)$
. Then, we have
$v_4\in N_C(H_1)$
and
$v_5\in N_C(H_2)$
. Let
$P_{v_1,v_4}$
be a
$(v_1,v_4)$
-path with interior in
$V(H_1)$
and let
$P_{v_2,v_5}$
be a
$(v_2,v_5)$
-path with interior in
$V(H_2)$
. Hence,
$v_1,P_{v_1,v_4},v_4,v_3,v_2,P_{v_2,v_5},v_5,v_6,v_1$
is a cycle with length at least
$8$
, which is a contradiction.
This completes the proof of Theorem 3.1.
A chordal graph is a simple graph in which every cycle of length greater than three has a chord. If
$\ell \ge 4$
is an integer, we say a graph is
$\ell $
-holed if all its holes have length exactly
$\ell $
. We say that
$X \subseteq V (G)$
is a clique cutset of G if
$G[X]$
is a complete graph and
$G\setminus X$
is disconnected. A vertex of G adjacent to all the other vertices of G is a universal vertex.
Let
$X,Y$
be disjoint subsets of
$V(G)$
. We denote by
$G[X,Y]$
the bipartite subgraph of G with vertex set
$X\cup Y$
and edge set the set of edges of G between
$X,Y$
. A half-graph is a bipartite graph with no induced two-edge matching. Let G be a graph with vertex set partitioned into sets
$W_1,\ldots ,W_{\ell }$
, with the following properties:
-
(i)
$W_1,\ldots ,W_{\ell }$
are nonnull cliques; -
(ii) for
$1\le i\le \ell $
,
$G[W_{i-1},W_i]$
is a half-graph (reading subscripts modulo
$\ell $
); -
(iii) for all distinct
$i,j\in [\ell ]$
, if there is an edge between
$W_i,W_j$
, then
$j=i\pm 1 \bmod \ell $
; -
(iv) for
$1\le i\le \ell $
, the graph
$G[W_i, W_{i-1}\cup W_{i+1}]$
is a half-graph.
We call such a graph a blow-up of an
$\ell $
-cycle.
Recently, Cook et al. provided some characterisations for
$\ell $
-holed graphs. We will use their results to complete our proof.
Lemma 3.2 (Cook et al. [Reference Cook, Horsfield, Preissmann, Robin, Seymour, Sintiari, Trotignon and Vuǎković4]).
Let G be a graph with no clique cutset and no universal vertex, and let
$\ell \geq 7$
. Then, G is
$\ell $
-holed if and only if either G is a blow-up of an
$\ell $
-cycle, or G is a blow-up of an
$\ell $
-framework.
The definition of a blow-up of an
$\ell $
-framework is complex and we refer to [Reference Cook, Horsfield, Preissmann, Robin, Seymour, Sintiari, Trotignon and Vuǎković4] for the details. The following lemma is well known and easy to verify.
Lemma 3.3 [Reference West12, page 231].
Let e be an edge of a cycle C in a chordal graph. Then, e forms a triangle with a third vertex of C.
Now we are ready to state and prove the main result.
Theorem 3.4. Let G be a non-Hamiltonian
$2$
-connected graph with
$\delta (G)\geq 3$
. If G is
$\ell $
-holed, then
$c'(G)+2\leq c(G)$
.
Proof. If G is a chordal graph or
$\ell \leq 6$
, then the result holds by Theorem 3.1. Suppose that G has a hole with length
$\ell \ge 7$
. Thus,
$c'(G)=\ell $
. By Lemma 3.2, we may assume that G admits a clique cutset, or a universal vertex, or G is a blow-up of a cycle of length
$\ell $
or G is a blow-up of an
$\ell $
-framework. By the definitions of a blow-up of a cycle of length
$\ell $
and a blow-up of an
$\ell $
-framework [Reference Cook, Horsfield, Preissmann, Robin, Seymour, Sintiari, Trotignon and Vuǎković4], it is not hard to verify in both of these cases that G has a cycle of length at least
$\ell +2$
. We only need to consider the remaining situations: G admits a clique cutset, or a universal vertex. Let G be a counterexample to Theorem 3.4 with minimum order.
Claim 3.1.
G is
$\ell $
-wheel-free.
Proof. To the contrary, we may assume that G contains an
$\ell $
-wheel W as a subgraph. Since G is non-Hamiltonian,
$V(G)\setminus V(W)\neq \emptyset $
. Let
$v\in V(G)\setminus V(W)$
. Since G is
$2$
-connected, there exist two
$(v,V(W))$
-paths
$Q_1,Q_2$
such that
$V(Q_1)\cap V(Q_2)= \emptyset $
. It is not hard to find a cycle with length at least
$\ell +2$
in
$V(W)\cup V(Q_1)\cup V(Q_2)$
, which is a contradiction.
By Claim 3.1, we now only need to consider the remaining case that G admits a clique cutset. Let S be a minimum clique cutset and let
$H_1,\ldots , H_t$
be the components of
$G-S$
. Let
$H_1$
be a component of
$G-S$
such that
$G[V(H_1)\cup S]$
contains an
$\ell $
-hole and let
$G'=G[V(H_1)\cup S]$
.
Claim 3.2.
$|S|=2$
.
Proof. Since G is
$2$
-connected, we have
$|S|\geq 2$
. Suppose that
$|S|\geq 3$
. Since S is a minimum clique cutset and
$|S|\geq 3$
, we have
$\delta (G')\geq 3$
. Note that
$G'$
is
$2$
-connected with fewer vertices than G. If
$G'$
is non-Hamiltonian, then
$c(G')\geq \ell +2$
. This implies that
$c(G)\geq c(G')\geq \ell +2$
, which is a contradiction. Thus,
$G'$
is Hamiltonian and
$c(G')\leq \ell +1$
. Since
$G'$
contains an
$\ell $
-hole,
$G'$
is an
$\ell $
-wheel. This implies that G contains an
$\ell $
-wheel, which contradicts Claim 3.1. This proves Claim 3.2.
For convenience, we may assume that
$S=\{u_1,u_2\}$
. Let
$C=v_1,v_2,\ldots ,v_{\ell },v_1 $
be an
$\ell $
-hole in
$G'$
.
Claim 3.3.
$V(C)\cap \{u_1,u_2\}=\emptyset .$
Proof. Otherwise, by symmetry, we may assume that
$u_1\in V(C)$
. If
$u_2\in V(C)$
, then
$u_1u_2\in E(C)$
. Since G is
$2$
-connected and
$\delta (G)\geq 3$
, there exists a
$(u_1,u_2)$
-path P with length at least
$3$
in
$G[V(H_2)\cup \{u_1,u_2\}]$
. It follows that
$G[V(C)\cup V(P)]$
is a cycle with length at least
$\ell +2$
, which is a contradiction. Hence,
$u_2\notin V(C)$
. Let
$P'$
be a
$(u_2,V(C))$
-path of
$G'$
such that
$u_1\notin V(P')$
. Since G is
$2$
-connected, such a path
$P'$
exists. For convenience, we may assume that
$u_1=v_1$
,
$v_j$
is a endpoint of P and
$j\leq {(\ell +1)}/{2}$
. Choose
$P'$
with j minimum. If
$j\leq 3$
, then
$v_1,P,u_2,P',v_j,v_{j+1},\ldots ,v_{\ell },v_{1}$
is a cycle with length at least
$\ell +2$
, which is a contradiction. Thus,
$j\geq 4$
. To forbid
$v_1,v_2,\ldots ,v_j,P',u_2,P,v_1$
from being a cycle with length at least
$\ell +2$
, we require that
$v_1,v_2,\ldots ,v_j,P',u_2,v_1$
has length at most
$\ell -1$
. This implies that the graph
$G[V(P')\cup \{v_1,\ldots , v_j\}]$
is a chordal graph. By Lemma 3.3, the edge
$v_1v_2$
forms a triangle with third vertex in
$\{v_1,\ldots ,v_j\}\cup V(P')$
. It follows that
$N_G(v_2)\cap V(P')\neq \emptyset $
, which contradicts the choice of j. This proves Claim 3.3.
Let
$P_1,P_2$
be two disjoint
$(S,V(C))$
-paths with
$u_i\in V(P_i)$
for
$i=1,2$
. Without loss of generality, we may assume that
$V(P_1)\cap V(C)=\{v_1\}$
and
$V(P_2)\cap V(C)=\{v_j\}$
. By symmetry, suppose that
$j\leq {(\ell +1)}/{2}$
. We may assume that
$P_1,P_2$
are chosen to minimise
$|V(P_1)|+|V(P_2)|$
prior to minimising j. By the previous analysis,
$j\geq 4$
and
$v_1,v_2,\ldots ,v_j,P_2,u_2,u_1,P_1,v_1 $
is a cycle with length at most
$\ell -1$
. This implies that
$G[V(P_1)\cup V(P_2)\cup \{v_1,\ldots , v_j\}]$
is a chordal graph. By Lemma 3.3, the edge
$v_{j-1}v_j$
forms a triangle with third vertex in
$\{v_1,\ldots ,v_{j-2}\}\cup V(P_2)\cup V(P_1)$
. By the choices of j and C as a chordless cycle,
$N_G(v_{j-1})\cap V(P_1)\neq \emptyset $
, say x, and hence,
$$ \begin{align*} v_{j-1},x,P_1[x,u_1],u_1,u_2,P_2,v_j,v_{j+1},\ldots,v_{j-1} \end{align*} $$
is a cycle with length at least
$\ell +2$
, which is a contradiction.
This completes the proof of Theorem 3.4.
Acknowledgement
The authors are grateful to Professor Xingzhi Zhan for his constant support and guidance.
