Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1709220 | Applied Mathematics Letters | 2011 | 4 Pages |
Abstract
Let GG be any graph, and let c(G)c(G) denote the circumference of GG. If, for every pair c1,c2c1,c2 of positive integers satisfying c1+c2=c(G)c1+c2=c(G), the vertex set of GG admits a partition into two sets V1V1 and V2V2 such that ViVi induces a graph of circumference at most cici, i=1,2i=1,2, then GG is said to be cc-partitionable. In [M.H. Nielsen, On a cycle partition problem, Discrete Math. 308 (2008) 6339–6347], it is conjectured that every graph is cc-partitionable. In this paper, we verify this conjecture for a graph with a longest cycle that is a dominating cycle. Moreover, we prove that GG is cc-partitionable if c(G)≥|V(G)|−3c(G)≥|V(G)|−3.
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Fengli Yang, Elkin Vumar,