董九英.任意长圈覆盖指定的独立的点[J].数学研究及应用,2009,29(3):391~394
任意长圈覆盖指定的独立的点
Any Long Cycles Covering Specified Independent Vertices
投稿时间:2007-03-24  修订日期:2007-11-22
DOI:10.3770/j.issn:1000-341X.2009.03.002
中文关键词:  点不相交的圈  度和条件  独立点.
英文关键词:vertex-disjoint cycle  degree sum condition  independent vertices.
基金项目:国家自然科学基金(No.10626029)
作者单位
董九英 江西财经大学信息管理学院数学系, 江西 南昌 330013 
摘要点击次数: 2867
全文下载次数: 1821
中文摘要:
      用变量 $\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.
查看全文  查看/发表评论  下载PDF阅读器