A note on a cycle partition problem

作者：Yang Fengli; Vumar Elkin^*

来源：Applied Mathematics Letters, 2011, 24(7): 1181-1184.

DOI：10.1016/j.aml.2011.02.003

• Circumference
• Partition
• Longest cycle
• Dominating cycle
• Path partition conjecture

Let G be any graph, and let c(G) denote the circumference of G. If, for every pair c(1), c(2) of positive integers satisfying c(1) + c(2) = c(G). the vertex set of G admits a partition into two sets V(1) and V(2) such that V(i) induces a graph of circumference at most c(i), i = 1,2, then G is said to be c-partitionable. In [M.H. Nielsen, On a cycle partition problem, Discrete Math. 308 (2008) 6339-6347], it is conjectured that every graph is c-partitionable. In this paper, we verify this conjecture for a graph with a longest cycle that is a dominating cycle. Moreover, we prove that G is c-partitionable if c(G) >= vertical bar V (G)vertical bar - 3.

• 出版日期2011-7
• 单位新疆大学