首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Hamiltonian and long paths in bipartite graphs with connectivity
Institution:1. School of Computer Science, South China Normal University, Guangzhou 510631, PR China;2. Student Affairs Department, South China Normal University, Guangzhou 510631, PR China
Abstract:Let G be a graph, ν(G) the order of G, κ(G) the connectivity of G and k a positive integer such that k(ν(G)?2)/2. Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A Hamiltonian path of a graph G is a spanning path of G. A bipartite graph G with vertex sets V1 and V2 is defined to be Hamiltonian-laceable if such that |V1|=|V2| and for every pair of vertices pV1 and qV2, there exists a Hamiltonian path in G with endpoints p and q, or |V1|=|V2|+1 and for every pair of vertices p,qV1,pq, there exists a Hamiltonian path in G with endpoints p and q. Let G be a bipartite graph with bipartition (X,Y). Define bn(G) to be a maximum integer such that 0bn(G)<min{|X|,|Y|} and (1) for each non-empty subset S of X, if |S||X|?bn(G), then |N(S)||S|+bn(G), and if |X|?bn(G)<|S||X|, then N(S)=Y; and (2) for each non-empty subset S of Y, if |S||Y|?bn(G), then |N(S)||S|+bn(G), and if |Y|?bn(G)<|S||Y|, then N(S)=X; and (3) bn(G)=0 if there is no non-negative integer satisfying (1) and (2).Let G be a bipartite graph with bipartition (X,Y) such that |X|=|Y| and bn(G)>0. In this paper, we show that if ν(G)2κ(G)+4bn(G)?4, then G is Hamiltonian-laceable; or if ν(G)>6bn(G)?2, then for every pair of vertices xX and yY, there is an (x,y)-path P in G with |V(P)|6bn(G)?2. We show some of its corollaries in k-extendable, bipartite graphs and a conjecture in k-extendable graphs.
Keywords:Hamiltonian path  Long path  Hamiltonian-laceable  Bipartite graph  Connectivity
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号