Sage Journals: Discover world-class research

Abstract

The length of dominating cycles is usually discussed in control problems. A dominating cycle of a graph G is a cycle C of G such that $V (G) - V (C)$ is an independent set. In this article, we prove that for any claw-free graph G with $δ (G) \geq 2$ , the length of longest dominating cycle is at least $\min {n, 2 | N C_{2} (G) | - 1}$ , where $N C_{2} (G)$ denotes the vertex set $N (u) \cup N (v)$ containing the minimum number of vertices for all vertices $u, v$ with $d (u, v) = 2$ in G.

Keywords

Control system dominating cycle claw-free graph

Introduction

The length of dominating cycles in graphs is usually discussed in control problems.^1–9 In this article, we only consider finite and simple graphs, and for the notation and terminology not defined here, please refer to Bondy and Murty¹⁰ The length of a longest cycle in a graph G is called the circumference of G. If a graph G contains no $K_{1, 3}$ induced subgraph, then G is claw-free. Let $N (v) = {u : uv \in E (G)}, N (u, v) = N (u) \cup N (v)$ and $N_{H} (S) = {v : v \in V (H) and v \in N (u) for some vertex u \in V (S)}, H, S \subseteq V (G)$ . A dominating cycle of a graph G is a cycle C of G such that $V (G) - V (C)$ is an independent set. Let $NC (G)$ denote the vertex set $N (u, v)$ containing the minimum number of vertices for all nonadjacent vertices $u, v \in V (G)$ , and $N C_{2} (G)$ denote the vertex set $N (u, v)$ with the minimum number of vertices for all vertices $u, v$ with $d (u, v) = 2$ .

Since the theory of dominating cycles can be applied to many fields, a lot of researchers put focus on it and have obtained many good results as follows.

Theorem 1.1.¹¹

If G is a 2-connected graph of order n with $σ_{3} (G) \geq n + 2$ , then the circumference of G is at least $min {n, 2 | NC (G) |}$ , where $σ_{3} (G)$ denotes the minimum sum degree of all three independent vertices in G.

Theorem 1.2.¹²

If G is a 2-connected graph of order n with $σ_{3} (G) \geq n + 2$ , then the circumference of G is at least $min {n, 2 | N C_{2} (G) |}$ , where $σ_{3} (G)$ denotes the minimum sum degree of all three independent vertices in G.

Theorem 1.3.¹³

If G is a 2-connected graph of order n containing a dominating cycle, which is not the Petersen graph, then G contains a dominating cycle of length at least $min {n, 2 | NC (G) |}$ .

Theorem 1.4.¹³

If G contains a dominating cycle with order n and $δ (G) \geq 2$ , then G contains a dominating cycle of length at least $min {n, 2 | N C_{2} (G) | - 3}$ .

Shen and Tian¹³ made the following conjecture:

Conjecture 1.5

If G contains a dominating cycle with order n and $δ (G) \geq 2$ , then

G contains a dominating cycle of length at least $min {n, 2 | N C_{2} (G) | - 1}$ if n is even;

G contains a dominating cycle of length at least $min {n, 2 | N C_{2} (G) | - 2}$ if n is odd.

In this article, we confirm the above conjecture holds for claw-free graphs as follows.

Theorem 1.6

If G is a claw-free graph of order n containing a dominating cycle with $δ (G) \geq 2$ , then the length of a longest dominating cycle is at least $\min {n, 2 | N C_{2} (G) | - 1}$ .

Proof of Theorem 1.6

For a cycle C with a positive direction and a vertex v on C, let $v^{+}$ denote the successor of v along the positive direction with $v^{+} v \in E (C)$ , and $v^{-}$ denote the predecessor of v with $v^{-} v \in E (C)$ . Similarly, $x^{+ +} = (x^{+})^{+}, x^{- -} = (x^{-})^{-}$ . uCv denotes the vertices on C from u to v along the positive direction, and $v C^{-} u$ denotes the vertices on C from u to v along the negative direction. Denote $N^{+} (u) = {v^{+} : v \in N_{C} (u)}$ , $N^{-} (u) = {v^{-} : v \in N_{C} (u)}$ .

To the contrary, suppose C is a longest dominating cycle with length at most $2 | N C_{2} (G) | - 2$ for a non-Hamiltonian claw-free graph G with $δ (G) \geq 2$ . In the following proof, assume $S = V (G) - V (C), y \in V (G) - V (C)$ and $N_{C} (y) = {x_{1}, x_{2}, \dots, x_{k}}$ . We can get the following results to prove Theorem 1.6.

Claim 1

For any vertex $x_{i} \in N_{C} (y)$ , $x_{i}^{+} x_{i}^{-} \in E (G), i \in {1, 2, \dots, k}$ .

Proof

If ${yx}_{i}^{-} \in E (G)$ , then there is a dominating cycle $C' = x_{i}^{-} y x_{i} {Cx}_{i}^{-}$ longer than C, a contradiction. Similarly, ${yx}_{i}^{+} \notin E (G)$ . Since $G [x_{i}, y, x_{i}^{+}, x_{i}^{-}] \neq K_{1, 3}, x_{i}^{+} x_{i}^{-} \in E (G)$ .□

Claim 2

For any two distinct vertices $x_{i}, x_{j} \in N_{C} (y), i, j \in {1, 2, \dots, k}$ , $x_{i}^{-} x_{j}^{-}, x_{i}^{+} x_{j}^{+} \notin E (G)$ .

Proof

Suppose $x_{i}^{-} x_{j}^{-} \in E (G)$ for some vertex $x_{i}, x_{j}$ , then G contains a longer dominating cycle $C' = x_{i} y x_{j} {Cx}_{i}^{-} x_{j}^{-} C^{-} x_{i}$ , a contradiction. Thus, $x_{i}^{-} x_{j}^{-} \notin E (G)$ . Similarly, $x_{i}^{+} x_{j}^{+} \notin E (G)$ .□

By the definition of dominating cycle, we can get the following result.

Claim 3

$N_{S} (y) = \emptyset$ and $N (y) = N_{C} (y)$ .

By Claim 1, Claim 2, and the maximality of C, it is easy to get the following results.

Claim 4

$x_{i}^{+ +} x_{j}^{+} \notin E (G)$ and $x_{i}^{- -} x_{j}^{-} \notin E (G)$ for $i, j \in {1, 2, \dots, k}$ .

Claim 5

For any $v \in V (G), d_{S} (v) \leq 1$ .

Proof

If $v \in S$ , then by the definition of dominating cycle, $d_{S} (v) \leq 1$ . Assume $v \in V (C)$ and without loss of generality, suppose $v = x_{1}$ and $y, y_{1} \in N_{S} (x_{1})$ . Obviously, $| N (y, y_{1}) | \geq | N C_{2} (G) |, | N^{+} (y, y_{1}) | \geq | N C_{2} (G) |$ . Suppose $z \in N (y, y_{1}) \cap N^{+} (y, y_{1})$ . By Claim 3, $z \in V (C)$ . Without loss of generality, assume $z \in N (y) \cap N^{+} (y_{1}) .$ Clearly, $x_{1} \neq z$ and $z^{+} z^{-}, z z^{- -} \in E (G)$ by Claim 1. Then, G contains a longer dominating cycle $x_{1} yz z^{- -} C^{-} x_{1}^{+} x_{1}^{-} C^{-} z^{+} z^{-} y_{1} x_{1}$ , a contradiction. It follows that $N (y, y_{1}) \cap N^{+} (y, y_{1}) = \emptyset$ . Then, $| V (C) | \geq | N (y, y_{1}) \cup N^{+} (y, y_{1}) | \geq | N (y, y_{1}) | + | N^{+} (y, y_{1}) | \geq 2 | N C_{2} (G) |$ , a contradiction.□

Claim 6

For any vertex $x_{i} \in N_{C} (y)$ , $N_{S} (x_{i}^{+}) = N_{S} (x_{i}^{-}) = \emptyset, i \in {1, 2, \dots, k}$ .

Proof

Without loss of generality, suppose $z \in N_{S} (x_{1}^{+})$ . Choose $z_{1} \in N_{C} (z)$ such that $x_{1} C z_{1}$ contains minimum vertices, that is, $N_{C} (z) \cap x_{1} {Cz}_{1}^{-} = \emptyset$ . Clearly, $x_{1}^{-} x_{1}^{+}, z_{1}^{-} z_{1}^{+} \in E (G), x_{1} x_{1}^{+ +} \in E (G)$ . Define a mapping f from $N_{C} (y, x_{1}^{+})$ to $V (C)$ by

f (w) = {\begin{matrix} w^{-} & if w \in x_{1}^{+} {Cz}_{1}^{-} \cup z_{1}^{+} {Cx}_{1}^{-} \\ w & if w = x_{1} \end{matrix}

For any vertex $w \in x_{1}^{+} {Cz}_{1}^{-} - {x_{1}^{+ +}}$ , by the choice of $z_{1}, wz \notin E (G)$ . If $w \in N (x_{1}^{+}) \cap x_{1}^{+} {Cz}_{1}^{-}$ , then $f (w) = w^{-}$ and $w^{-} z_{1}^{-} \notin E (G)$ , otherwise G contains a longer dominating cycle $C' = x_{1}^{+} z z_{1} C x_{1} x_{1}^{+ +} C w^{-} z_{1}^{-} C^{-} {wx}_{1}^{+}$ , a contradiction. If $w \in N (y) \cap x_{1}^{+} {Cz}_{1}^{-}$ , then $f (w) = w^{-}$ and $w^{-} z_{1}^{-} \notin E (G)$ , otherwise G contains a longer dominating cycle $C' = x_{1} z z_{1} C x_{1} yw C^{-} z_{1}^{-} w^{-} C^{-} x_{1}$ , a contradiction.

If $w \in N (y) \cap z_{1}^{+} {Cx}_{1}^{-}$ , then $f (w) = w^{-}$ and $w^{-} z_{1}^{-} \notin E (G)$ , otherwise G contains a longer dominating cycle $C' = x_{1}^{+} z z_{1} C w^{-} z_{1}^{-} C^{-} x_{1}^{+ +} x_{1} {ywCx}_{1}^{-} x_{1}^{+}$ , a contradiction. Similarly, $w^{-} z \notin E (G)$ if $w \in N (y) \cap z_{1}^{+} {Cx}_{1}^{-}$ . If $w \in N (x_{1}^{+}) \cap z_{1}^{+} {Cx}_{1}^{-}$ , then $f (w) = w^{-}$ and $w^{-} z_{1}^{-} \notin E (G)$ , otherwise G contains a longer dominating cycle $x_{1}^{+} z z_{1} C w^{-} z_{1}^{-} C^{-} x_{1}^{+ +} x_{1} C^{-} {wx}_{1}^{+}$ , a contradiction. Similarly, $w^{-} z \notin E (G)$ if $w \in N (x_{1}^{+}) \cap z_{1}^{+} {Cx}_{1}^{-}$ .

Clearly, if $w = x_{1}$ , then $wz \notin E (G)$ , and by the proof of Claim 2, ${wz}_{1}^{-} \notin E (G)$ . It follows that $f (N_{C} (y, x_{1}^{+})) \cap N_{C} (z, z_{1}^{-}) \subseteq {x_{1}^{+}}$ . By Claim 5, $| f (N_{C} (y, x_{1}^{+})) | = | N_{C} (y, x_{1}^{+}) | \geq | N (y, x_{1}^{+}) | - | {z, x_{1}^{+}} | = | N C_{2} (G) | - 2$ and $N_{C} (z, z_{1}^{-}) | \geq | N C_{2} (G) | - 1$ . By the definition of f and the maximality of C, $x_{1}^{-}, x_{j}^{+} \notin f (N_{C} (y, x_{1}^{+}))$ for some vertex $x_{j} \in N_{C} (y) \ {x_{1}}$ . Thus, $| V (C) | \geq | {x_{1}^{-}, x_{j}^{+}} | + | f (N_{C} (y, x_{1}^{+})) \cup N_{C} (z, z_{1}^{-}) | \geq 2 | N C_{2} (G) | - 1$ , a contradiction.□

Proof of Theorem 1.6

For $i \in {1, \dots, k}$ , let $T_{i} = x_{i}^{+} {Cx}_{i + 1}^{-}, W_{11} = N^{-} (x_{1}^{+}) \cap T_{1}, W_{12} = N (x_{2}^{+}) \cap T_{1}$ , and $W_{i 1} = N (x_{1}^{+}) \cap T_{i}, W_{i 2} = N^{-} (x_{2}^{+}) \cap T_{i}$ , for $i = 2, 3, \dots, k$ . Clearly, $W_{i 1} \cup W_{i 2} \subseteq T_{i}$ and $W_{i 1} \cap W_{i 2} = \emptyset, i \in {1, \dots, k}$ . By Claim 2 and Claim 4, $x_{i}^{+} \notin W_{i 1} \cup W_{i 2}$ . It follows that

\begin{matrix} | N_{T} (x_{1}^{+}) | + | N_{T} (x_{2}^{+}) | \\ = \sum_{i = 1}^{k} (| W_{i 1} | + | W_{i 2} |) = \sum_{i = 1}^{k} (| W_{i 1} \cup W_{i 2} |) \leq | T_{1} | \\ + | T_{2} | + \sum_{i = 1}^{k} (| T_{i} | - 1) = | T | - k + 2 \\ = | V (C) | - 2 k + 2 \leq 2 | N C_{2} (G) | - 2 k - 2 \end{matrix}

By Claim 6, $| N C_{2} (G) | \leq | N (x, u_{i}) | = | N (x) | + | N_{T} (x_{i}^{+}) | = k + | N_{T} (x_{i}^{+}) | (i = 1, 2)$ , then $| N_{T} (x_{1}^{+}) | + | N_{T} (x_{2}^{+}) | \geq | 2 N C_{2} (G) | - 2 k$ , a contradiction. It follows that Theorem 1.6 holds.

Footnotes

Handling Editor: Zhaojie Ju

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the Joint Fund of Liaoning Province Natural Science Foundation (Grant No. SY2016012) and Educational Commission of Liaoning Province (Grant No. L2014239).

References

Yang

Wang

Cheng

et al . Neural-learning based telerobot control with guaranteed performance. IEEE T Cybernetics 2017; 47: 3148–3159.

Wang

Liu

et al . Fuzzy tracking adaptive control of discrete-time switched nonlinear systems. Fuzzy Set Syst 2017; 316: 35–48.

Xiao

Yang

et al . Robust stabilization of a wheeled mobile robot using model predictive control based on neurodynamics optimization. IEEE T Ind Electron 2017; 64: 505–516.

Liu

Tong

SC.

Barrier Lyapunov functions for Nussbaum gain adaptive control of full state constrained nonlinear systems. Automatica 2017; 76: 143–152.

Liu

Tong

et al . Neural approximation-based adaptive control for a class of nonlinear nonstrict feedback discrete-time systems. IEEE T Neur Net Lear 2017; 28: 1531–1541.

Yang

Jiang

et al . Neural control of bimanual robots with guaranteed global stability and motion precision. IEEE T Ind Inform 2017; 13: 1162–1171.

Liu

et al . Adaptive controller design-based ABLF for a class of nonlinear time-varying state constraint systems. IEEE T Syst Man Cyb 2017; 47: 1546–1553.

Yang

Luo

Pan

et al . Personalized variable gain control with tremor attenuation for robot teleoperation. IEEE T Syst Man Cyb 2017; 47: 3136–3147.

Liu

Tong

et al . Neural network control-based adaptive learning design for nonlinear systems with full-state constraints. IEEE T Neur Net Lear 2016; 27: 1562–1571.

10.

Bondy

Murty

Graph theory with applications. Vol. 67. New York: American Elsevier, 1976.

11.

Bauer

Fan

Veldman

HJ.

Hamiltonian properties of graphs with large neighborhood unions. Discrete Math 1991; 96: 33–50.

12.

Bondy

JA.

Longest paths and cycles in graphs of high degree. Technical report, University of Waterloo, Waterloo, ON, 1980.

13.

Shen

Tian

Long dominating cycles in graphs. Discrete Math 1997; 177: 287–294.

The length of dominating cycle of claw-free graph

Abstract

Keywords

Introduction

Theorem 1.1. 11

Theorem 1.2. 12

Theorem 1.3. 13

Theorem 1.4. 13

Conjecture 1.5

Theorem 1.6

Proof of Theorem 1.6

Claim 1

Proof

Claim 2

Proof

Claim 3

Claim 4

Claim 5

Proof

Claim 6

Proof

Proof of Theorem 1.6

Footnotes

Declaration of conflicting interests

Funding

References

Theorem 1.1.¹¹

Theorem 1.2.¹²

Theorem 1.3.¹³

Theorem 1.4.¹³