Any Long Cycles Covering Specified Independent Vertices
Received:March 24, 2007  Revised:November 22, 2007
Key Words: vertex-disjoint cycle   degree sum condition   independent vertices.  
Fund Project:the National Natural Science Foundation of China (No.\,10626029).
Author NameAffiliation
DONG Jiu Ying School of Information Technology, Jiangxi University of Finance and Economics, Jiangxi 330013, China 
Hits: 2868
Download times: 1821
Abstract:
      An invariant $\sigma_2(G)$ of a graph is defined as follows: $\sigma_2(G):=\min\{ d(u) d(v)|u,v\in V(G),uv \not\in E(G), u\neq v\}$ is the minimum degree sum of nonadjacent vertices~(when $G$ is a complete graph, we define $\sigma_2(G)=\infty$). Let $k$, $s$ be integers with $k\geq 2$ and $s\geq 4$, $G$ be a graph of order $n $ sufficiently large compared with $s$ and $k$. We show that if $\sigma_2(G)\geq n k-1$, then for any set of $k$ independent vertices $v_1,\ldots,v_k$, $G$ has $k$ vertex-disjoint cycles $C_1,\ldots, C_k$ such that $ |C_i|\leq s$ and $v_i\in V(C_i)$ for all $1\leq i \leq k$. The condition of degree sum $\sigma_2(G)\geq n k-1$ is sharp.
Citation:
DOI:10.3770/j.issn:1000-341X.2009.03.002
View Full Text  View/Add Comment