Some results on placing bipartite graphs of maximum degree two.

Abstract: Bipartite graphs and are bi-placeabe if there is a bijection such that and for every edge ). We prove that if G and H are two bipartite graphs of order such that the sizes of G and H satisfy and , and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that for integers p and such that for and every bipartite balanced graph G of order 2p and size at least contains mutually vertex disjoint cycles , unless . [Copyright &y& Elsevier]