A Sufficient Condition for 2-Distance-Dominating Cycles

Xinman Wang, Linyu Li

School of Mathematics and Statistics, Shandong Normal University, Jinan, China.

DOI: 10.4236/eng.2022.143010                

Abstract

A cycle C of a graph G is a m-distance-dominating cycle if for all vertices of . Defining

denotes the minimum value of the degree sum of any k independent vertices of G. In this paper, we prove that if G is a 3-connected graph on n vertices, and if , then every longest cycle is m-distance-dominating cycles.

Keywords

Degree Sums, Distance Dominating Cycles, Insertible Vertex

1. Introduction

Let $G=\left(V\mathrm{,}E\right)$ be a graph and H be a subgraph of G, for a $S\subseteq V\left(G\right)$, let $N_H\left(S\right)=N\left(S\right)\cap V\left(H\right)$. For any $x,y\in V\left(G\right)$, $Y\subseteq V\left(G\right)$, $xy$ denotes the edge with ends x and y, an $\left(x\mathrm{,}Y\right)$ -path denotes a path starting at x and ending at Y. We denote by $\alpha \left(G\right)$ and $\kappa \left(G\right)$ the independence number and the connectivity of G, respectively.

Let C be a cycle of G, and denote by $\stackrel{\to }{C}$ the cycle C with a given orientation. For $v\in V\left(C\right)$, define $v^{+}$ and $v^{-}$ to be the successor and predecessor of v on C, define $v^{+i}$ and $v^{-i}$ to be the i-th successor and predecessor of v on C, respectively. In particular, we write $A^{+i}=\left\{a^{+i}\mathrm{<mi>\; </mi>\; <mo>\; |\; </mo>\; <mi>\; </mi>}a\in A\right\}$ and $A^{-i}=\left\{a^{-i}\mathrm{<mi>\; </mi>\; <mo>\; |\; </mo>\; <mi>\; </mi>}a\in A\right\}$. If $u,v\in V\left(G\right)$, we denote by $u\stackrel{\to }{C}v$ the consecutive vertices of C from u to v in the direction specified by $\stackrel{\to }{C}$. The same path, in reverse order, is denoted by $v\stackrel{\leftarrow }{C}u$. We will consider $u\stackrel{\to }{C}v$ and $v\stackrel{\leftarrow }{C}u$ both as paths and as vertex sets.

We use $\min \left\{d_G\left(v_1\mathrm{,}{v}_2\right)\mathrm{<mi>\; </mi>\; <mo>\; :\; </mo>\; <mi>\; </mi>}{v}_1\in V\left(H_1\right)\mathrm{,\; <mi>\; </mi>}{v}_2\in V\left(H_2\right)\right\}$ to denote the distance $d_G\left(H_1\mathrm{,}{H}_2\right)$ between $H_1$ and $H_2$, $H_1$ and $H_2$ are all the subgraphs of G, where $d_G\left(v_1\mathrm{,}{v}_2\right)$ denotes the length of a shortest path between $v_1$ and $v_2$ in G. A subgraph H of G is m-dominating if for all $x\in V\left(G\right)$, $d_G\left(x\mathrm{,}H\right)\le m$. For an integer $k\ge 2$, define

${\sigma }_k=\min \left\{{\displaystyle \underset{i=1}{\overset{k}{\sum }}}d\left(x_i\right)\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left\{x_1,\cdots ,x_k\right\}\mathrm{<mi>\; </mi>}\text{is an independent set of}\mathrm{<mi>\; </mi>}G\right\}$

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 $k\ge 2$ . If any $k+1$ independent vertices $x_i\left(0\le i\le k\right)$ with $N\left(x_i\right)\cap N\left(x_j\right)=\varnothing$ $\left(0\le i\ne j\le k\right)$ have degree-sum ${\displaystyle {\sum }_{i=0}^k}d\left(x_i\right)\ge n-2k$ , 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 $k+1$ , whose vertices are pairwise at distance at least $2m+2$ . Then G has an m-distance-dominating cycle.

The circumference $c\left(G\right)$ 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 $\kappa \left(G\right)=k\ge 2$ . If $c\left(G\right)\ge \left(2m+2\right)k-1$ , then every longest cycle of G is a m-distance-dominating cycle.

A cycle C is m-edge-dominating if for all $e\in E\left(G\right)$, $d_G\left(e\mathrm{,}C\right)\le m$. Clearly, a cycle is 0-edge-dominating (or simply dominating) if every edge of G is incident with a vertex of C, $G-V\left(C\right)$ 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 ${\sigma }_3\left(G\right)\ge n+2$ , 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 $k\ge 2$ . If ${\sigma }_{k+1}\left(G\right)\mathrm{<mo>\; >\; </mo>}\left(n+1\right)\left(k+1\right)/3$ , 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 ${\sigma }_4\left(G\right)>4n/3-4/3$ , then every longest cycle is a 2-distance-dominating cycle.

1. Key Lemmas

Lemma 1 [6] Let $P=u_1{u}_2\cdots u_l$ and $Q_1\mathrm{,}\cdots \mathrm{,}{Q}_m$ be $m+1$ pairwise vertex disjoint paths of a graph G. If for any $v\in V\left(Q_i\right)$ , there are $u_k\mathrm{,\; <mi>\; </mi>}{u}_{k+1}\in N\left(v\right)$ such that $\left\{u_k\mathrm{,}{u}_{k+1}\right\}⊈N\left(v^{\prime }\right)$ for any $v^{\prime }\in V\left(Q_j\right)$ with $j\ne i$ , then G has a $\left(u_1\mathrm{,\; <mi>\; </mi>}{u}_l\right)$ -path with $V\left(P\right)\cup \left({\displaystyle {\cup }_{i=1}^{m}V\left(Q_i\right)}\right)$ as its vertex set.

A k-fan from x to Y is a family of k internal disjoints $\left(x\mathrm{,}Y\right)$ -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 $Y\subseteq V\left(G\right)\backslash x$ 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, $k\ge 2$. Let C be a longest cycle of G with a given orientation. Let $R=V\left(G\right)-V\left(C\right)$, assume H is a component of $G-V\left(C\right)$ and $N_C\left(H\right)=\left\{h_1\mathrm{,}{h}_2\mathrm{,}\cdots \mathrm{,}{h}_t\right\}$, where the subscripts increase with the orientation of C.

A vertex $u\in h_i^{+}\stackrel{\to }{C}{h}_{i+1}^{-}$ is insertible if there exist vertices $v\mathrm{,}{v}^{+}\in h_{i+1}\stackrel{\to }{C}{h}_i$ such that $uv\mathrm{,}u{v}^{+}\in E\left(G\right)$ and the edge $v{v}^{+}\in E\left(G\right)$ is called an insertion edge of u, and noninsertible otherwise.

For any i with $1\le i\le t$, if each vertex of $h_i^{+}\stackrel{\to }{C}{h}_{i+1}^{-}$ is insertible, then by Lemma 1, G has an $\left(h_i\mathrm{,}{h}_{i+1}\right)$ -path P such that $V\left(P\right)=V\left(C\right)$. Thus, there is a $\left(h_i\mathrm{,}{h}_{i+1}\right)$ -path L with internal vertices in H and $\left|L\right|\ge 3$. We find $ℂ=h_{i}P{h}_{i+1}L{h}_i$ is a cycle longer than C, contradiction. Thus, $h_i^{+}\stackrel{\to }{C}{h}_{i+1}^{-}$ contains at least one noninsertible vertex. Write $a_i$ as the first noninsertible vertex occurring on $h_i^{+}\stackrel{\to }{C}{h}_{i+1}^{-}$, $A_i=h_i^{+}\stackrel{\to }{C}{a}_i$. For any $v\in V\left(H\right)$, we let $A_v=\left\{a_i\mathrm{<mi>\; </mi>\; <mo>\; |\; </mo>\; <mi>\; </mi>}{h}_i\in N\left(v\right)\right\}$.

Lemma 3 [6] 1) There is no $\left(x\mathrm{,}y\right)$ -path without internal vertices in $V\left(C\right)\cup V\left(H\right)$ for any $x\in A_i$ and $y\in A_j$ with $i\ne j$ ;

2) $N_P^{-}\left(A_i\right)\cap N_P\left(A_j\right)=N_Q\left(A_i\right)\cap N_Q^{-}\left(A_j\right)=\varnothing$, where $P=a_i^{+}\stackrel{\to }{C}{h}_j$ and $Q=a_j^{+}\stackrel{\to }{C}{h}_i$.

Lemma 4 [6] Suppose $v_1\mathrm{,}{v}_2\in V\left(H\right)$ with $v_1\ne v_2$ , $a_i\in A_{v_1}$ and $a_j\in A_{v_2}$ with $i\ne j$ . Then 1) $a_i^{+}\notin N\left(A_j\right)$ and $a_j^{+}\notin N\left(A_i\right)$ ;

2) $N_P^{-2}\left(A_i\right)\cap N_P\left(A_j\right)=N_Q\left(A_i\right)\cap N_Q^{-2}\left(A_j\right)=\varnothing$, where $P=a_i^{+}\stackrel{\to }{C}{h}_j$ and $Q=a_j^{+}\stackrel{\to }{C}{h}_i$.

2. Proof of Theorem 6

Let G be a graph of order n with connectivity $\kappa \left(G\right)\ge 3$, satisfying ${\sigma }_4\left(G\right)>\left(4n-4\right)/3$. Let C be a longest cycle with a given orientation and $\left|C\right|\ge 3$ since G is 3-connected. Assuming there is a vertex $u\in V\left(G\right)\backslash C$ such that $d\left(u\mathrm{,}C\right)\ge 3$. By Lemma 2, there is a 3-fan $\mathfrak{B}=\left\{P_1\mathrm{,}{P}_2\mathrm{,}{P}_3\right\}$ in G from u to $V\left(C\right)$ and the length of $P_i$ is at least 3, $i=1,2,3$. Let $R=V\left(G\right)-V\left(C\right)$, and H is a component of $G-V\left(C\right)$ containing u. By the definition of k-fan, we get $\left|H\right|\ge 7$. Let $x_i=V\left(P_i\right)\cap V\left(C\right)$, $i=1,2,3$, $a_i$ is the noninsertible vertex as the same definition on the previous section, $A_i=x_i^{+}\stackrel{\to }{C}{a}_i$, $i=1,2,3$. And $v_i$ is $x_i$ ’s first neighbor on the path $P_i$, $i=1,2,3$.

Claim 1 $A_i\cap N_C\left(H\right)=\varnothing$, $i=1,2,3$ .

proof Without loss of generality, suppose there is a vertex $x\in A_1$ such that $x\in N_C\left(H\right)$. Let $Q=x_1^{+}\stackrel{\to }{C}x$, $P=x^{+}\stackrel{\to }{C}{x}_1$, then all the vertex on Q are insertible. Thus we can get a $\left(x_1\mathrm{,}x\right)$ -path $P^{\prime }$ such that $V\left(P^{\prime }\right)=V\left(C\right)$ by Lemma 1. Let L denote a $\left(x_1\mathrm{,}x\right)$ -path with internal vertices in H, and $\left|L\right|\ge 3$. We can get a new cycle $ℂ=x_1{P}^{\prime }xL{x}_1$ longer than C. (Contradiction) $\square$

Claim 2 $d\left(v_1\right)+d\left(a_1\right)+d\left(a_2\right)\le n$.

proof We first find that $\left\{a_1\mathrm{,}{a}_2\right\}\cap N_C\left(H\right)=\varnothing$ by Claim 1, $a_1$ and $a_2$ have no common neighbors on $R-H$ since Lemma 3(1). Thus, $N_R\left(v_1\right)$, $N_R\left(a_1\right)$, $N_R\left(a_2\right)$ are pairwise disjoint. And since $d\left(u\mathrm{,}C\right)\ge 3$, $u{v}_1\notin E\left(G\right)$. Therefore, we have the inequality as follows.

$d_R\left(v_1\right)+d_R\left(a_1\right)+d_R\left(a_2\right)\le \left|R\right|-2.$

Similarly, by Claim 1 and Lemma 3(1), we have

$d_{A_1\cup A_2}\left(v_1\right)+d_{A_1\cup A_2}\left(a_1\right)+d_{A_1\cup A_2}\left(a_2\right)\le \left|A_1\right|-1+\left|A_2\right|-1.$

Next let $P=a_1^{+}\stackrel{\to }{C}{x}_2$, $Q=a_2^{+}\stackrel{\to }{C}{x}_1$, $U_1=A_{v_1}\cap V\left(P\right)$, $U_2=A_{v_1}\cap V\left(Q\right)$. Since $N_C\left(v_1\right)\cap A_i=\varnothing$, $i=1,2,3$, then $A_{v_1}\backslash \left\{a_1\mathrm{,}{a}_2\right\}\subseteq U_1\cup U_2$. Note that $d_C\left(v_1\right)=\left|A_{v_1}\right|$, thus $\left|U_1\right|+\left|U_2\right|\ge d_C\left(v_1\right)-2$. Let $U_1=\left\{a_{v_{11}},a_{v_{12}},\cdots ,a_{v_{1t}}\right\}$, $t\le n$. We will analyse $d_P\left(a_1\right)+d_P\left(a_2\right)$ by considering the following cases.

Case 1. For any $a_{v_{1j}}^{+}\in U_1^{+}$, $a_{v_{1j}}^{+}\notin N_P\left(a_1\right)$, which implies $a_{v_{1j}}\notin N_P^{-}\left(a_1\right)$, $j\mathrm{<mi>\; </mi>}=\mathrm{<mi>\; </mi>1},2,\cdots ,t$.

By Lemma 3(1), we have $a_{v_{1j}}\notin N_P\left(a_2\right)$, and thus for any $a_{v_{1j}}\in U_1$, $j\mathrm{<mi>\; </mi>}=\mathrm{<mi>\; </mi>1},2,\cdots ,t$, we have $a_{v_{1j}}\notin N_P^{-}\left(a_1\right)\cup N_P\left(a_2\right)$. And by Lemma 3(2), $N_P^{-}\left(a_1\right)\cap N_P\left(a_2\right)=\varnothing$. Hence $N_P^{-}\left(a_1\right)\cup N_P\left(a_2\right)\subseteq V\left(P\right)\cup \left\{a_1\right\}\backslash U_1$. Therefore, $d_P\left(a_1\right)+d_P\left(a_2\right)=\left|N_P^{-}\left(a_1\right)\right|+\left|N_P\left(a_2\right)\right|\le \left|P\right|+1-\left|U_1\right|\mathrm{.}$

Case 2. There exist some $a_{v_{1j}}^{+}\in U_1^{+}$, $a_{v_{1j}}^{+}\in N_P\left(a_1\right)$, say $\left\{a_{v_{i1}}^{+}\mathrm{,}{a}_{v_{i2}}^{+}\mathrm{,}\cdots \mathrm{,}{a}_{v_{ir}}^{+}\right\}$, $r\le t$.

Then we can note that $a_{v_{ij}}^{++}\notin N\left(a_1\right)$. Since $a_1$ is noninsertible, which implies $a_{v_{ij}}^{+}\notin N_P^{-}\left(a_1\right)$, $j\mathrm{<mi>\; </mi>}=\mathrm{<mi>\; </mi>1},2,\cdots ,r$, $r\le t$. And by Lemma 4(1), we know $a_{v_{ij}}^{+}\notin N_P\left(a_2\right)$. Thus $a_{v_{ij}}^{+}\notin N_P^{-}\left(a_1\right)\cup N_P\left(a_2\right)$. On the other hand, for the remaining vertices, $a_{v_{1j}}\in U_1\backslash \left\{a_{v_{i1}}\mathrm{,}{a}_{v_{i2}}\mathrm{,}\cdots \mathrm{,}{a}_{v_{ir}}\right\}$, similar to case 1, we have $a_{v_{1j}}\notin N_P^{-}\left(a_1\right)\cup N_P\left(a_2\right)$. In addition, $a_{v_{1j}}^{+}\ne a_{v_{1j+1}}$, since there are some $x\in N_C\left(H\right)$ on $a_{v_{1j}}\stackrel{\to }{C}{a}_{v_{1j+1}}$. And by Lemma 3(2), $N_P^{-}\left(a_1\right)\cap N_P\left(a_2\right)=\varnothing$. Therefore, we have the inequality as follows.

$d_P\left(a_1\right)+d_P\left(a_2\right)=\left|N_P^{-}\left(a_1\right)\right|+\left|N_P\left(a_2\right)\right|\le \left|P\right|+1-\left|U_1\right|\mathrm{.}$

By Lemma 3(1) and Lemma 4(1), for any $a_{1j}\in U_2$, we have $a_{1j}\notin N_Q\left(a_1\right)\cup N_Q^{-}\left(a_2\right)$. So we have the inequality as follows.

$d_Q\left(a_1\right)+d_Q\left(a_2\right)=\left|N_Q\left(a_1\right)\right|+\left|N_Q^{-}\left(a_2\right)\right|\le \left|Q\right|+1-\left|U_2\right|\mathrm{.}$

Therefore,

$\begin{array}{l}d\left(v_1\right)+d\left(a_1\right)+d\left(a_2\right)\\ \le \left(d_P\left(v_1\right)+\left|P\right|+1-\left|U_1\right|\right)+\left(d_Q\left(v_1\right)+\left|Q\right|+1-\left|U_2\right|\right)+\left(\left|A_1\right|+\left|A_2\right|-2\right)+\left(\left|R\right|-2\right)\\ =d_C\left(v_1\right)+\left(\left|P\right|+\left|Q\right|+\left|A_1\right|+\left|A_2\right|+\left|R\right|\right)-\left(\left|U_1\right|+\left|U_2\right|\right)-2\\ \le n+d_C\left(v_1\right)-\left(d_C\left(v_1\right)-2\right)-2\\ =n.\end{array}$

$\square$

By a similar argument as Claim 2, Claim 3 holds.

Claim 3 $d\left(v_1\right)+d\left(a_1\right)+d\left(a_3\right)\le n$.

Claim 4 $d\left(v_1\right)+d\left(a_2\right)+d\left(a_3\right)\le n$.

proof Similarly, by Claim 1 and Lemma 3(1), we have

$d_R\left(v_1\right)+d_R\left(a_2\right)+d_R\left(a_3\right)\le \left|R\right|-2.$

$d_{A_2\cup A_3}\left(v_1\right)+d_{A_2\cup A_3}\left(a_2\right)+d_{A_2\cup A_3}\left(a_3\right)\le \left|A_2\right|-1+\left|A_3\right|-1.$

Let $P=a_2^{+}\stackrel{\to }{C}{x}_3$, $Q=a_3^{+}\stackrel{\to }{C}{x}_2$. $U_1=A_{v_1}\cap V\left(P\right)$, $U_2=A_{v_1}\cap V\left(Q\right)$. Then we have $\left|U_1\right|+\left|U_2\right|\ge d_C\left(v_1\right)-2$. And by Lemma 3(2), $N_P^{-}\left(a_2\right)\cap N_P\left(a_2\right)=\varnothing$.

Let $U_1=\left\{a_{v_{11}},a_{v_{12}},\cdots ,a_{v_{1t}}\right\}$, for any $a_{v_{1j}}\in U_1$, we have $a_{v_{1j}}^{+}\notin N_P\left(a_2\right)$ by Lemma 4(1), that is $a_{v_{1j}}\notin N_P^{-}\left(a_2\right)$, $j=1,2,\cdots ,t$. And for any $a_{v_{1j}}\in U_1$, we have $a_{v_{1j}}\notin N_P\left(a_3\right)$ by Lemma 3(1). Therefore, $a_{v_{1j}}\notin N_P^{-}\left(a_2\right)\cup N_P\left(a_3\right)$, $j=1,2,\cdots ,t$.

By Lemma 3(2), $N_P^{-}\left(a_2\right)\cap N_P\left(a_3\right)=\varnothing$. Hence,

$N_P^{-}\left(a_2\right)\cup N_P\left(a_3\right)\subseteq V\left(P\right)\cup \left\{a_2\right\}\backslash U_1$.

Thus we have the inequality as follows,

$d_P\left(a_2\right)+d_P\left(a_3\right)=\left|N_P^{-}\left(a_2\right)\right|+\left|N_P\left(a_3\right)\right|\le \left|P\right|+1-\left|U_1\right|\mathrm{.}$

Furthermore, according to the symmetry of P and Q,

$d_Q\left(a_2\right)+d_Q\left(a_3\right)\le \left|Q\right|+1-\left|U_2\right|\mathrm{.}$

Therefore,

$\begin{array}{l}d\left(v_1\right)+d\left(a_2\right)+d\left(a_3\right)\\ \le \left(d_P\left(v_2\right)+\left|P\right|+1-\left|U_1\right|\right)+\left(d_Q\left(v_1\right)+\left|Q\right|+1-\left|U_2\right|\right)+\left(\left|A_2\right|+\left|A_3\right|-2\right)+\left(\left|R\right|-2\right)\\ =d_C\left(v_1\right)+\left(\left|P\right|+\left|Q\right|+\left|A_2\right|+\left|A_3\right|+\left|R\right|\right)-\left(\left|U_1\right|+\left|U_2\right|\right)-2\\ \le n+d_C\left(v_1\right)-\left(d_C\left(v_1\right)-2\right)-2\\ =n\mathrm{.}\end{array}$

$\square$

Claim 5 $d\left(a_1\right)+d\left(a_2\right)+d\left(a_3\right)\le n-4$.

proof Let $P=a_1^{+}\stackrel{\to }{C}{x}_2$, $Q=a_2^{+}\stackrel{\to }{C}{x}_3$, $M=a_3^{+}\stackrel{\to }{C}{x}_1$. By Lemma 3(2) and Lemma 4(2), note that $N_P^{-2}\left(a_1\right)$, $N_P\left(a_2\right)$, $N_P^{-}\left(a_3\right)$ are pairwise disjoint. So $N_P^{-2}\left(a_1\right)\cup N_P\left(a_2\right)\cup N_P^{-}\left(a_3\right)\subseteq a_1^{-}\stackrel{\to }{C}{x}_2$, which implies

$d_P\left(a_1\right)+d_P\left(a_2\right)+d_P\left(a_3\right)\le \left|P\right|+2.$

According to the symmetry of P, Q and R, we have

$d_Q\left(a_1\right)+d_Q\left(a_2\right)+d_Q\left(a_3\right)\le \left|Q\right|+2.$

$d_M\left(a_1\right)+d_M\left(a_2\right)+d_M\left(a_3\right)\le \left|M\right|+2.$

By Lemma 3(1), we have

$d_{A_1\cup A_2\cup A_3}\left(a_1\right)+d_{A_1\cup A_2\cup A_3}\left(a_2\right)+d_{A_1\cup A_2\cup A_3}\left(a_3\right)\le \left|A_1\right|-1+\left|A_2\right|-1+\left|A_3\right|-1.$

At last, by Claim 1 and Lemma 3(1), we have

$d_R\left(a_1\right)+d_R\left(a_2\right)+d_R\left(a_3\right)\le \left|R\right|-\left|H\right|\mathrm{.}$

Note that $\left|H\right|\ge 7$, thus

$\begin{array}{l}d\left(a_1\right)+d\left(a_2\right)+d\left(a_3\right)\\ \le \left(\left|P\right|+2\right)+\left(\left|Q\right|+2\right)+\left(\left|M\right|+2\right)+\left(\left|A_1\right|+\left|A_2\right|+\left|A_3\right|-3\right)+\left(\left|R\right|-\left|H\right|\right)\\ =\left(\left|P\right|+\left|Q\right|+\left|M\right|+\left|A_1\right|+\left|A_2\right|+\left|A_3\right|+\left|R\right|\right)+3-\left|H\right|\\ =n+3-\left|H\right|\\ \le n-4.\end{array}$

$\square$

By Lemma 3(1) and Claim 1, $\left\{v_1\mathrm{,}{a}_1\mathrm{,}{a}_2\mathrm{,}{a}_3\right\}$ is an independent set in G. By Claim 2-5, we have

$d\left(v_1\right)+d\left(a_1\right)+d\left(a_2\right)+d\left(a_3\right)\le \frac{4}{3}n-\frac{4}{3}\mathrm{,}$

a contradiction.

This completes the proof of Theorem 6.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bondy, J.A. and Fan, G. (1987) A Sufficient Condition for Dominating Cycles. Discrete Mathematics, 67, 205-208. https://doi.org/10.1016/0012-365X(87)90029-X
[2]	Broersma, H.J. (1988) Existence of -Cycles and -Paths. Journal of Graph Theory, 12, 499-507. https://doi.org/10.1002/jgt.3190120405
[3]	Fraisse, P. (1988) A Note on Distance-Dominating Cycles. Discrete Math, 71, 89-92. https://doi.org/10.1016/0012-365X(88)90033-7
[4]	Fang, Y. and Xiong, L. (2021) Circumference of a Graph and Its Distance Dominating Longest Cycles. Discrete Mathematics, 344, Article ID: 112196. https://doi.org/10.1016/j.disc.2020.112196
[5]	Bondy, J.A. (1980) Longest Paths and Cycles in Graphs of High Degree. Research Report CORR 80-16, University of Waterloo, Ontario.
[6]	Wu, Y., Chen, Y. and Edein Cheng, T.C. (2021) Degree Sums and Dominating Cycles. Discrete Mathematics, 344, Article ID: 112224. https://doi.org/10.1016/j.disc.2020.112224
[7]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, Berlin. https://doi.org/10.1007/978-1-84628-970-5