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). |
|
Hits: 2938 |
Download times: 1889 |
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 |
|
|
|