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

# 3-biplacement of bipartite graphs

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.
Lech Adamus, Edyta Leśniak, Beata Orchel, 3-biplacement of bipartite graphs, Opuscula Math. 28, no. 3 (2008), 223-231

a .bib file (BibTeX), a .ris file (RefMan), a .enw file (EndNote)
or export to RefWorks.

ISSN 1232−9274, e-ISSN 2300−6919, DOI http://dx.doi.org/10.7494/OpMath
Contact: opuscula@agh.edu.pl