任意长圈覆盖指定的独立的点

Any Long Cycles Covering Specified Independent Vertices

中文关键词:  点不相交的圈  度和条件  独立点.

英文关键词:vertex-disjoint cycle  degree sum condition  independent vertices.

中文摘要:

      用变量 $\sigma_2(G)$ 来记一个图中不相邻的两点的度和的最小值, (如果 $G$ 是完全图,那我们记$\sigma_2(G)=\infty$.令$k$和$s$是两个整数有$k\geq 2$, $s\geq 4$, $G$是一个图它的阶相对于$k$和$s$ 来说 充分大。 我们证明：假如 $\sigma_2(G)\geq n k-1$， 那么对于图$G$中任意$k$ 个独立的点$v_1,\cdots,v_k$, $G$ 有 $k$ 个点不相交的 圈$C_1,\cdots, C_k$ 使得 这 $ k$ 个不交的圈中每个圈的长度不超过 $s$ 并且满足 $v_i\in V(C_i)$ 对于所有的$ 1

英文摘要:

      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.