MUTUAL PLACEMENT OF BIPARTITE GRAPHS

Let G=(L,R,E) and H=(L',R',E') be bipartite graphs. A bijection phi:L or R-->L' or R' is said to be a biplacement of G and H if phi(L)=L' an d phi(x)phi(y) is-not-an-element-of E' for every edge xy of G. A bipla cement of G and its copy is called a 2-placement of G. We prove that, with some exceptions, every bipartite graph G of order n and size at m ost n-2 has a 2-placement. We. also give some sufficient conditions fo r bipartite graphs G and H to have a biplacement.