On the cyclability of graphs

摘要

Given a graph G = (V, E) and A_1,A_2,..., A_r, mutually disjoint nonempty subsets of V where |A_i| ≤ |V|/r for each i, we say that G is spanning equi-cyclable with respect to A_1, A_2, ..., A_r if there exist mutually disjoint cycles C_1, C_2,..., C_r that span G such that C_i contains A_i for every i and C_i contains either 「|V|/r」 vertices or 「|V|/r」 vertices. Moreover, G is r-spanning-equi-cyclable if G is spanning equi-cyclable with respect to A_1, A_2,..., 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 κ-spanning equi-cyclable for k = 1,2,..., τ but is not (r + 1)-spanning-equi-cyclable. Another approach on the restriction of the A_i's is the following. We say that G = (V,E) is r-cyclable of order t if it is cyclable with respect to A_1, A2,..., A_r for any r nonempty mutually disjoint subsets A_1, A_2,..., A_r of V such that |A_1 U A_2U.. .UA_r| ≤ t. The r-cyclability of G is t if G is r-cyclable of order k for k = r, r+1,..., 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,..., 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 other related problems.