Covering a bipartite graph with cycles passing through given edges
Covering a bipartite graph with cycles passing through given edges
复制标题
用穿过给定边的循环覆盖二部图
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Hong Wang
中科院分区：
文献类型：
--
作者：
Hong Wang
我们提出了一个猜想：对于每一个整数k 2:: 2，存在N(k)，如果G = （Vb \12； E）是一个二部图，IV11 = 1\121 = N 2: N(k)和d(x) + d(y) 2: N + k，对于G的每一对非相邻顶点x和y， x E V1和y E \12，那么对于任意k个独立边el，…， k (G)，存在k个顶点不相交循环G1，…， Gk在G中使得E E（Gi）对于所有E {i，…， k}， V(G1 U···U Gk) = V(G)。如果这个猜想成立，G度的条件是尖锐的。本文在k = 2的情况下证明了这个猜想。
We propose a conjecture: for each integer k 2:: 2, there exists N (k) such that if G = (Vb \12; E) is a bipartite graph with IV11 = 1\121 = n 2: N(k) and d( x) + d(y) 2: n + k for each pair of non-adjacent vertices x and y of G with x E V1 and y E \12, then for any k independent edges el, ... , ek of G, there exist k vertex-disjoint cycles G1, ... , Gk in G such that ei E E(Gi ) for all i E {I, ... , k} and V(G1 U··· U Gk ) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper.