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


Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph
Authors:Jin Yan  Guizhen Liu
Institution:1. School of Mathematics & System Sciences, Shandong University, Jinan, 250100, China
Abstract:The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V 1,V 2;E) be a bipartite graph with |V 1|=|V 2|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with xV 1 and yV 2, then, for any k independent edges e 1,…,e k of G, G contains k vertex-disjoint quadrilaterals C 1,…,C k such that e i E(C i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V 1|=|V 2|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C 1,…,C k containing specified edges of G.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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