Opuscula Math. 28, no. 3 (2008), 223-231

Opuscula Mathematica

# 3-biplacement of bipartite graphs

Edyta Leśniak
Beata Orchel

Abstract. Let $$G=(L,R;E)$$ be a bipartite graph with color classes $$L$$ and $$R$$ and edge set $$E$$. A set of two bijections $$\{\varphi_1 , \varphi_2\}$$, $$\varphi_1 , \varphi_2 :L \cup R \to L \cup R$$, is said to be a $$3$$-biplacement of $$G$$ if $$\varphi_1(L)= \varphi_2(L) = L$$ and $$E \cap \varphi_1^*(E)=\emptyset$$, $$E \cap \varphi_2^*(E)=\emptyset$$, $$\varphi_1^*(E) \cap \varphi_2^*(E)=\emptyset$$, where $$\varphi_1^*$$, $$\varphi_2^*$$ are the maps defined on $$E$$, induced by $$\varphi_1$$, $$\varphi_2$$, respectively. We prove that if $$|L| = p$$, $$|R| = q$$, $$3 \leq p \leq q$$, then every graph $$G=(L,R;E)$$ of size at most $$p$$ has a $$3$$-biplacement.

Keywords: bipartite graph, packing of graphs, placement, biplacement.

Mathematics Subject Classification: 05C70.

Full text (pdf)

• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland
• Edyta Leśniak
• Beata Orchel
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland
• Revised: 2008-02-15.
• Accepted: 2008-03-01. 