交叉立方体网络的双不交圈覆盖泛圈性

Two-Disjoint-Cycle-Cover Pancyclicity of Crossed Cube

摘要: 设$r_1,r_2$ 为满足$r_2\ge r_1\ge 0$ 的两个整数，在图$G$ 中若对任意两个顶点$u,v\in V\left(G\right)$ 以及任意满足$r_1\le l\le r_2$ 的整数$l$ ，在图$G$ 中总存在两个顶点不交的圈$J_1$ 和$J_2$ 满足$\left|V\left(J_1\right)\right|=l$ ，$\left|V\left(J_2\right)\right|=\left|V\left(G\right)\right|-l$ ，且$u\in V\left(J_1\right)$ ，$v\in V\left(J_2\right)$ ，则图$G$ 被称为是$\left[r_1,r_2\right]$ -双不交圈覆盖泛圈图。本文研究$n$ 维交叉立方体网络的双不交圈覆盖泛圈性，并证明$n\ge 3$ 时，任意$n$ 维交叉立方体网络都是$\left[4,2^{n-1}\right]$ -双不交圈覆盖泛圈图，且结果达到最优。

Abstract: Let $r_1,r_2$ be two integers with $r_2\ge r_1\ge 0$ . A graph $G$ is called two-disjoint-cycle-cover (2-DCC for short) $\left[r_1,r_2\right]$ -pancyclic if for any two vertices $u,v\in V\left(G\right)$ and any integer $l$ satisfying $r_1\le l\le r_2$ , there exist two vertex-disjoint cycles$J_1$ and $J_2$ in $G$ such that $\left|V\left(J_1\right)\right|=l$ , $\left|V\left(J_2\right)\right|=\left|V\left(G\right)\right|-l$ , $u\in V\left(J_1\right)$ , $v\in V\left(J_2\right)$ . In this paper, we study the 2-DCC pancyclicity of the$n$ -dimensional crossed cube and prove that for $n\ge 3$ , every $n$ -dimensional crossed cube network is $\left[4,2^{n-1}\right]$ -two-disjoint-cycle-cover pancyclic, and the result is optimal.