Two-Disjoint-Cycle-Cover Pancyclicity of Augmented Cubes

doi:10.1007/s40305-023-00474-4

Abstract

Abstract: A graph G is two-disjoint-cycle-cover \begin{document}$ [r_{1},r_{2}] $\end{document}-pancyclic, if for any integer \begin{document}$ \ell $\end{document} satisfying \begin{document}$ r_{1} \leqslant \ell \leqslant r_{2} $\end{document}, there exist two vertex-disjoint cycles \begin{document}$ C_{1} $\end{document} and \begin{document}$ C_{2} $\end{document} in G such that the lengths of \begin{document}$ C_{1} $\end{document} and \begin{document}$ C_{2} $\end{document} are \begin{document}$ \ell $\end{document} and \begin{document}$ |V(G)|-\ell $\end{document}, respectively, where |V(G)| denotes the number of vertices in G. More specifically, a graph G is two-disjoint-cycle-cover vertex \begin{document}$ [r_{1},r_{2}] $\end{document}-pancyclic (resp. edge \begin{document}$ [r_{1},r_{2}] $\end{document}-pancyclic) if for any two distinct vertices \begin{document}$ u_{1}, u_{2} \in V(G) $\end{document} (resp. two vertex-disjoint edges \begin{document}$ e_{1}, e_{2} \in E(G) $\end{document}), there exist two vertex-disjoint cycles \begin{document}$ C_{1} $\end{document} and \begin{document}$ C_{2} $\end{document} in G such that for every integer \begin{document}$ \ell $\end{document} satisfying \begin{document}$ r_{1} \leqslant \ell \leqslant r_{2} $\end{document}, \begin{document}$ C_{1} $\end{document} contains \begin{document}$ u_{1} $\end{document} (resp. \begin{document}$ e_{1} $\end{document}) with length \begin{document}$ \ell $\end{document} and \begin{document}$ C_{2} $\end{document} contains \begin{document}$ u_{2} $\end{document} (resp. \begin{document}$ e_{2} $\end{document}) with length \begin{document}$ |V(G)|-\ell $\end{document}. In this paper, we consider the problem of two-disjoint-cycle-cover pancyclicity of the n-dimensional augmented cube \begin{document}$ AQ_n $\end{document} and obtain the following results: \begin{document}$ AQ_n $\end{document} is two-disjoint-cycle-cover \begin{document}$ [3,2^{n-1}] $\end{document}-pancyclic for \begin{document}$ n \geqslant 3 $\end{document}. Moreover, \begin{document}$ AQ_n $\end{document} is two-disjoint-cycle-cover vertex \begin{document}$ [3,2^{n-1}] $\end{document}-pancyclic for \begin{document}$ n \geqslant 3 $\end{document}, and \begin{document}$ AQ_n $\end{document} is two-disjoint-cycle-cover edge \begin{document}$ [4,2^{n-1}] $\end{document}-pancyclic for \begin{document}$ n \geqslant 3 $\end{document}.

Key words: Pancyclic, Vertex-disjoint cycles, Disjoint-cycle cover, Augmented cube

CLC Number:

05C38

Shu-Jie Zhou, Min Xu. Two-Disjoint-Cycle-Cover Pancyclicity of Augmented Cubes[J]. Journal of the Operations Research Society of China, 2025, 13(2): 555-573.

TrendMD

References

[1] Kung, T.L., Chen, H.C.: Complete cycle embedding in crossed cubes with two-disjoint-cycle-cover pancyclicity. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 98(12), 2670-2676 (2015)
[2] Kung, T.L., Chen, H.C., Lin, C.H., Hsu, L.H.: Three types of two-disjoint-cycle-cover pancyclicity and their applications to cycle embedding in locally twisted cubes. Comput. J. 64(1), 27-37 (2021)
[3] Wei, C., Hao, R.X., Chang, J.M.: Two-disjoint-cycle-cover bipancyclicity of balanced hypercubes. Appl. Math. Comput. 381, 125305 (2020)
[4] Niu, R.C., Xu, M., Lai, H.J.: Two-disjoint-cycle-cover vertex bipancyclicity of the bipartite generalized hypercube. Appl. Math. Comput. 400, 126090 (2021)
[5] Choudum, S.A., Sunitha, V.: Augmented cubes. Networks 40(2), 71-84 (2002)
[6] Hsu, H.C., Chiang, L.C., Tan, J.J.M., Hsu, L.H.: Fault hamiltonicity of augmented cubes. Parallel Comput. 31(1), 131-145 (2005)
[7] Cheng, B.L., Fan, J.X., Lyu, Q., Lin, C.K., Li, X.Y., Chen, G.: Constructing node-independent spanning trees in augmented cubes. Fund. Inform. 176(2), 103-128 (2020)
[8] Cheng, B.L., Fan, J.X., Lin, C.K., Wang, Y., Wang, G.J.: An improved algorithm to construct edge-independent spanning trees in augmented cubes. Discrete Appl. Math. 277, 55-70 (2020)
[9] Chen, M.R., Naserasr, R.: The optimal routing of augmented cubes. Inform. Process. Lett. 136, 59-63 (2018)
[10] Chen, Y.C., Chen, M.H., Tan, J.J.M.: Maximally local connectivity and connected components of augmented cubes. Inform. Sci. 273, 387-392 (2014)
[11] Dong, Q., Wang, X.: How many triangles and quadrilaterals are there in an n-dimensional augmented cube. Theoret. Comput. Sci. 771, 93-98 (2019)
[12] Gu, M.M., Chang, J.M., Hao, R.X.: Strong Menger connectedness of augmented k-ary n-cubes. Comput. J. 64(5), 812-825 (2021)
[13] Kandekar, S.A., Mane, S.A., Waphare, B.N.: One-to-one conditional path covers on augmented cubes. J. Ramanujan Math. Soc. 36(4), 309-323 (2021)
[14] Ma, M.J., Yu, J.G.: Edge-disjoint paths in faulty augmented cubes. Discrete Appl. Math. 294, 108-114 (2021)
[15] Xu, X.R., Zhang, H.F., Zhang, S.J., Yang, Y.S.: Fault-tolerant panconnectivity of augmented cubes

\begin{document}$ AQ_n $\end{document}

. Internat. J. Found. Comput. Sci. 30(8), 1247-1278 (2019)
[16] Zhang, H.F., Xu, X.R., Wang, Z.M., Zhang, Q., Yang, Y.S.:

\begin{document}$ (2n-3) $\end{document}

-fault-tolerant Hamiltonian connectivity of augmented cubes

\begin{document}$ AQ_n $\end{document}

. AIMS Math. 6(4), 3486-3511 (2021)
[17] Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, London (2008)
[18] Bondy, J.A.: Pancyclic graphs I. J. Combin. Theory Ser. B 11(1), 80-84 (1971)