ArticleOriginal scientific text

Title

2-placement of (p,q)-trees

Authors 1

Affiliations

  1. 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

Bibliography

  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.
Pages:
23-36
Main language of publication
English
Received
2000-12-19
Accepted
2002-03-07
Published
2003
Exact and natural sciences