Bi-Cycle Extendable Through a Given Set in Balanced Bipartite Graphs

Hao Li 1, Mei Lu 1, and Feng Tian 2
1 Department of Mathematical Sciences, Tsinghua University, Beijing 100084, P. R. China
2 Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, P. R. China


Abstract     Full Text  PDF

Let $G = (X, Y ;E)$ be a balanced bipartite graph of order $2n$. The path cover number $pc(H)$ of a graph $H$ is the minimum number of vertex-disjoint paths that use up all the vertices of $H$. $S \subseteq V(G)$ is called a balanced set of $G$ if $\mid S\cap X\mid = \mid S\cap Y\mid$. In this talk, we will give some sufficient conditions for a balanced bipartite graph $G$ satisfying that for every balanced set $S$, there is a bi-cycle of every length from $|S| + 2pc((S))$ up to $2n$ through $S$.