# 2-placement of (p,q)-trees

Discussiones Mathematicae Graph Theory (2003)

- Volume: 23, Issue: 1, page 23-36
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBeata Orchel. "2-placement of (p,q)-trees." Discussiones Mathematicae Graph Theory 23.1 (2003): 23-36. <http://eudml.org/doc/270503>.

@article{BeataOrchel2003,

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.
},

author = {Beata Orchel},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {tree; bipartite graph; packing graph},

language = {eng},

number = {1},

pages = {23-36},

title = {2-placement of (p,q)-trees},

url = {http://eudml.org/doc/270503},

volume = {23},

year = {2003},

}

TY - JOUR

AU - Beata Orchel

TI - 2-placement of (p,q)-trees

JO - Discussiones Mathematicae Graph Theory

PY - 2003

VL - 23

IS - 1

SP - 23

EP - 36

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

LA - eng

KW - tree; bipartite graph; packing graph

UR - http://eudml.org/doc/270503

ER -

## References

top- [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. Zbl0479.05028
- [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. Zbl0791.05080
- [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. Zbl0861.05019
- [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. Zbl0773.05084

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.