东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2006, Vol. 27 ›› Issue (9): 1054-1058.DOI: -

• 论著 • 上一篇    下一篇

有圈二部图覆盖的一个结果

车向凯;王立华;   

  1. 东北大学理学院;沈阳农业大学基础部 辽宁沈阳110004;辽宁沈阳110161
  • 收稿日期:2013-06-23 修回日期:2013-06-23 出版日期:2006-09-15 发布日期:2013-06-23
  • 通讯作者: Che, X.-K.
  • 作者简介:-
  • 基金资助:
    辽宁省科学技术基金资助项目(20022021)

Result of covering a bipartite graph with cycles

Che, Xiang-Kai (1); Wang, Li-Hua (2)   

  1. (1) School of Sciences, Northeastern University, Shenyang 110004, China; (2) Basic Department, Shenyang Agricultural University, Shenyang 110161, China
  • Received:2013-06-23 Revised:2013-06-23 Online:2006-09-15 Published:2013-06-23
  • Contact: Che, X.-K.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

587

摘要： H.Wang猜想,对于任意整数k≥2,存在N(k)使得二部图G=(V1,V2,E)中,V1=V2=n≥N(k),且对于G中任意一对不相邻的顶点x∈V1,y∈V2,有d(x)+d(y)≥n+k,那么,对于G中任意k个独立边e1,e2,e3,…,ek,存在顶点不重的k个圈C1,C2,…,Ck,使得ei∈E(Ci),i∈{1,2,…,k}和V(C1∪C2∪…∪Ck)=V(G).H.Wang及J.A.Bondy对k=2,3时证明了猜想成立,本文对k=4证明了猜想的正确性.

关键词: 简单图, 二部图, 路, 圈, 覆盖

Abstract: H. Wang conjectured that for each integer k &le 2 there exists N(k) such that if G = (V1, V21, E) is a bipartite graph in which |V1| = |V2| = n &le N(k) and d(x) + d(y) &le n + k for any pair of nonadjacentvertices x∈V1 and y∈V2, then for any k independent edges e1, e2, e3, &mellip;ek in G there exist k vertex-disjoint cycles C1, C2, &mellip;, Ck such that ei∈E(Ci), i∈{l, 2, &mellip;, k} and V(C1UC2U&mellip;UCk) = V(G). This conjecture has been verified if k = 2, 3 by H. Wang and J.A.Bondy, but we prove it if k = 4.

中图分类号: