Discussiones Mathematicae Graph Theory 33(1) (2013) 193-201
doi: 10.7151/dmgt.1651

Dedicated to Mietek Borowiecki on the occasion of his seventieth birthday: best wishes and thanks for all!

[BIBTex] [PDF] [PS]

A note on uniquely embeddable forests

Justyna Otfinowska and Mariusz Woźniak

AGH University of Science and Technology
Faculty of Applied Mathematics
Al. Mickiewicza 30, 30-059 Krakow, Poland


Let F be a forest of order n. It is well known that if F ≠ Sn, a star of order n, then there exists an embedding of F into its complement  ̄F. In this note we consider a problem concerning the uniqueness of such an embedding.

Keywords: packings of graphs, uniquely embeddable graphs

2010 Mathematics Subject Classification: 05C70.


[1]B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory (B) 25 (1978) 105--124, doi: 10.1016/0095-8956(78)90030-8.
[2]D. Burns and S. Schuster, Every (p,p-2) graph is contained in its complement, J. Graph Theory 1 (1977) 277--279, doi: 10.1002/jgt.3190010308.
[3]D. Burns and S. Schuster, Embedding (n,n-1) graphs in their complements, Israel J. Math. 30 (1978) 313--320, doi: 10.1007/BF02761996.
[4]B. Ganter, J. Pelikan and L. Teirlinck, Small sprawling systems of equicardinal sets, Ars Combin. 4 (1977) 133--142.
[5]N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory (B) 25 (1978) 295--302, doi: 10.1016/0095-8956(78)90005-9.
[6]J. Otfinowska and M. Woźniak, A note on uniquely embeddable forests, Preprint MD (www.ii.uj.edu.pl/preMD/) 046 (2010) }.
[7]M. Woźniak, Embedding graphs of small size, Discrete Applied Math. 51 (1994) 233--241, doi: 10.1016/0166-218X(94)90112-0.
[8]M. Woźniak, Packing three trees, Discrete Math. 150 (1996) 393--402, doi: 10.1016/0012-365X(95)00204-A.
[9]M. Woźniak, A note on uniquely embeddable graphs, Discuss. Math. Graph Theory 18 (1998) 15--21, doi: 10.7151/dmgt.1060.
[10]M. Woźniak, Packing of graphs---some recent results and trends, Studies, Math. Series 16 (2003) 115--120.
[11]M. Woźniak, Packing of graphs and permutation---a survey, Discrete Math. 276 (2004) 379--391, doi: 10.1016/S0012-365X(03)00296-6.
[12]M. Woźniak, A note on uniquely embeddable cycles, Preprint MD ( www.ii.uj.edu.pl/preMD/) 047 (2010) }.
[13]H.P. Yap, Packing of graphs---a survey, Discrete Math. 72 (1988) 395--404, doi: 10.1016/0012-365X(88)90232-4 .

Received 2 January 2012
Revised 5 October 2012
Accepted 8 October 2012