PDF

Discussiones Mathematicae Graph Theory 23(1) (2003) 23-36
DOI: https://doi.org/10.7151/dmgt.1183

2-PLACEMENT OF (p,q)-TREES

Beata Orchel

University of Mining and Metallurgy
Al. Mickiewicza 30
30-059 Kraków, Poland

Abstract

Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q−1.

Let G = (L,R;E) and H = (L′,R′;E′) be two (p,q)-tree. A bijection f:L∪R→ L′∪R′ is said to be a biplacement of G and H if f(L) = L′ and f(x)f(y) ∉ E′ for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which are not 2-placeable.

Keywords: tree, bipartite graph, packing graph.

2000 Mathematics Subject Classification: 05C35.

References

[1]	B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).
[2]	R.J. Faudree, C.C. Rousseau, R.H. Schelp and S. Schuster, Embedding graphs in their complements, Czechoslovak Math. J. 31 (106) (1981) 53-62.
[3]	J.-L. Fouquet and A.P. Wojda, Mutual placement of bipartite graphs, Discrete Math. 121 (1993) 85-92, doi: 10.1016/0012-365X(93)90540-A.
[4]	M. Makheo, J.-F. Saclé and M. Woźniak, Edge-disjoint placement of three trees, European J. Combin. 17 (1996) 543-563, doi: 10.1006/eujc.1996.0047.
[5]	B. Orchel, Placing bipartite graph of small size I, Folia Scientiarum Universitatis Technicae Resoviensis 118 (1993) 51-58.
[6]	H. Wang and N. Saver, Packing three copies of a tree into a complete graph, European J. Combin. 14 (1993) 137-142.

Received 19 December 2000
Revised 7 March 2002