1. Introduction
Let
be a graph and H be a subgraph of G, for a
, let
. For any
,
,
denotes the edge with ends x and y, an
-path denotes a path starting at x and ending at Y. We denote by
and
the independence number and the connectivity of G, respectively.
Let C be a cycle of G, and denote by
the cycle C with a given orientation. For
, define
and
to be the successor and predecessor of v on C, define
and
to be the i-th successor and predecessor of v on C, respectively. In particular, we write
and
. If
, we denote by
the consecutive vertices of C from u to v in the direction specified by
. The same path, in reverse order, is denoted by
. We will consider
and
both as paths and as vertex sets.
We use
to denote the distance
between
and
,
and
are all the subgraphs of G, where
denotes the length of a shortest path between
and
in G. A subgraph H of G is m-dominating if for all
,
. For an integer
, define
In 1987, Bondy [1] considered the existence of k-connected graphs of order n.
Theorem 1 [1] Let G be a k-connected graph on n vertices, where
. If any
independent vertices
with
have degree-sum
, then G has a 1-distance-dominating cycle.
In 1988, Broersma [2] and Fraisse [3] proved some results about m-distance-dominating cycles.
Theorem 2 [2] [3] Let G be a k-connected graph with no set of cardinality
, whose vertices are pairwise at distance at least
. Then G has an m-distance-dominating cycle.
The circumference
of a graph G is the length of the longest cycle on the graph. In 2021, Xiong [4] considered the relation between the graph circumference and m-distance-dominating cycle, and proved a sufficient condition that every longest cycle in k-connected graph is m-distance-dominating cycle.
Theorem 3 [4] Let G be a graph with
. If
, then every longest cycle of G is a m-distance-dominating cycle.
A cycle C is m-edge-dominating if for all
,
. Clearly, a cycle is 0-edge-dominating (or simply dominating) if every edge of G is incident with a vertex of C,
is edgeless. It is very popular to decide whether a longest cycle is (0-edge) dominating. Bondy [5] gave a sufficient condition such that every longest cycle of 2-connected graph is (0-edge) dominating.
Theorem 4 [5] Let G be a 2-connected graph on n vertices. If
, then every longest cycle is dominating.
Wu [6] considered the same problem for k-connected graphs and established the following.
Theorem 5 [6] Let G be k-connected graph on n vertices with
. If
, then every longest cycle is dominating.
In this paper, we consider the general version for degree sums condition that guarantees that every longest cycle is a 2-distance-dominating cycle in 3-connected graphs. Our main result is the following.
Theorem 6 Let G be a 3-connected graph on n vertices. If
, then every longest cycle is a 2-distance-dominating cycle.
1. Key Lemmas
Lemma 1 [6] Let
and
be
pairwise vertex disjoint paths of a graph G. If for any
, there are
such that
for any
with
, then G has a
-path with
as its vertex set.
A k-fan from x to Y is a family of k internal disjoints
-paths whose terminal vertices are distinct. The following lemma known as Fan Lemma establishes an useful property of k-connected graphs.
Lemma 2 [7] Let G be a k-connected graph, let x be a vertex of G, and let
be a set of at least k vertices of G. Then there exists a k-fan in G from x to Y.
Next, we assume G be a k-connected non-hamiltonian graph of order n,
. Let C be a longest cycle of G with a given orientation. Let
, assume H is a component of
and
, where the subscripts increase with the orientation of C.
A vertex
is insertible if there exist vertices
such that
and the edge
is called an insertion edge of u, and noninsertible otherwise.
For any i with
, if each vertex of
is insertible, then by Lemma 1, G has an
-path P such that
. Thus, there is a
-path L with internal vertices in H and
. We find
is a cycle longer than C, contradiction. Thus,
contains at least one noninsertible vertex. Write
as the first noninsertible vertex occurring on
,
. For any
, we let
.
Lemma 3 [6] 1) There is no
-path without internal vertices in
for any
and
with
;
2)
, where
and
.
Lemma 4 [6] Suppose
with
,
and
with
. Then 1)
and
;
2)
, where
and
.
2. Proof of Theorem 6
Let G be a graph of order n with connectivity
, satisfying
. Let C be a longest cycle with a given orientation and
since G is 3-connected. Assuming there is a vertex
such that
. By Lemma 2, there is a 3-fan
in G from u to
and the length of
is at least 3,
. Let
, and H is a component of
containing u. By the definition of k-fan, we get
. Let
,
,
is the noninsertible vertex as the same definition on the previous section,
,
. And
is
’s first neighbor on the path
,
.
Claim 1
,
.
proof Without loss of generality, suppose there is a vertex
such that
. Let
,
, then all the vertex on Q are insertible. Thus we can get a
-path
such that
by Lemma 1. Let L denote a
-path with internal vertices in H, and
. We can get a new cycle
longer than C. (Contradiction)
Claim 2
.
proof We first find that
by Claim 1,
and
have no common neighbors on
since Lemma 3(1). Thus,
,
,
are pairwise disjoint. And since
,
. Therefore, we have the inequality as follows.
Similarly, by Claim 1 and Lemma 3(1), we have
Next let
,
,
,
. Since
,
, then
. Note that
, thus
. Let
,
. We will analyse
by considering the following cases.
Case 1. For any
,
, which implies
,
.
By Lemma 3(1), we have
, and thus for any
,
, we have
. And by Lemma 3(2),
. Hence
. Therefore,
Case 2. There exist some
,
, say
,
.
Then we can note that
. Since
is noninsertible, which implies
,
,
. And by Lemma 4(1), we know
. Thus
. On the other hand, for the remaining vertices,
, similar to case 1, we have
. In addition,
, since there are some
on
. And by Lemma 3(2),
. Therefore, we have the inequality as follows.
By Lemma 3(1) and Lemma 4(1), for any
, we have
. So we have the inequality as follows.
Therefore,
By a similar argument as Claim 2, Claim 3 holds.
Claim 3
.
Claim 4
.
proof Similarly, by Claim 1 and Lemma 3(1), we have
Let
,
.
,
. Then we have
. And by Lemma 3(2),
.
Let
, for any
, we have
by Lemma 4(1), that is
,
. And for any
, we have
by Lemma 3(1). Therefore,
,
.
By Lemma 3(2),
. Hence,
.
Thus we have the inequality as follows,
Furthermore, according to the symmetry of P and Q,
Therefore,
Claim 5
.
proof Let
,
,
. By Lemma 3(2) and Lemma 4(2), note that
,
,
are pairwise disjoint. So
, which implies
According to the symmetry of P, Q and R, we have
By Lemma 3(1), we have
At last, by Claim 1 and Lemma 3(1), we have
Note that
, thus
By Lemma 3(1) and Claim 1,
is an independent set in G. By Claim 2-5, we have
a contradiction.
This completes the proof of Theorem 6.