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 x∈V 1 and y∈V 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 等数据库收录! |
|