On the Cyclability of Graphs

Abstract

Given a graph $G=(V,E)$ and $A_1,A_2,\dots ,A_r$, mutually disjoint nonempty subsets of $V$ where $|A_i|\le |V|/r$ for each $i$, we say that $G$ is spanning equi-cyclable with respect to $A_1,A_2,\dots ,A_r$ if there exist mutually disjoint cycles $C_1,C_2,\dots ,C_r$ that span $G$ such that $C_i$ contains $A_i$ for every $i$ and $C_i$ contains either $\lfloor |V|/r\rfloor$ vertices or $\lceil |V|/r\rceil$ vertices. Moreover, $G$ is $r$-$spanning-equicyclable$ if $G$ is spanning equi-cyclable with respect to $A_1,A_2,\dots ,A_r$ for every such mutually disjoint nonempty subsets of $V$. We define the spanning equi-cyclability of $G$ to be $r$ if $G$ is $k$-spanning-equicyclable for $k=1,2,\dots ,r$ but is not $(r+1)$-spanning-equicyclable. Another approach on the restriction of the $A_i$’s is the following. We say that $G=(V,E)$ is $r$-$cyclableoforder$ $t$ if it is cyclable with respect to $A_1,A_2,\dots ,A_r$ for any $r$ nonempty mutually disjoint subsets $A_1,A_2,\dots ,A_r$ of $V$ such that $|A_1\cup A_2\cup \dots \cup A_r|\le t$. The $r$-cyclability of $G$ is $t$ if $G$ is $r$-cyclable of order $k$ for $k=r,r+1,\dots ,t$ but is not $r$-cyclable of order $t+1$. On the other hand, the cyclability of $G$ of order $t$ is $r$ if $G$ is $k$-cyclable of order $t$ for $k=1,2,\dots ,r$ but is not $(r+1)$-cyclable of order $t$. In this paper, we study sufficient conditions for spanning equi-cyclability and $r$-cyclability of order $t$ as well as other related problems.