2-placement of (p,q)-trees

Beata Orchel

Discussiones Mathematicae Graph Theory (2003)

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

Abstract

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

How to cite

top

Beata 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. [1] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978). 
  2. [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. [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. [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. [5] B. Orchel, Placing bipartite graph of small size I, Folia Scientiarum Universitatis Technicae Resoviensis 118 (1993) 51-58. 
  6. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.