Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We say that a graph G is packable into a complete graph Kn if there are two edge-disjoint subgraphs of Kn both isomorphic to G. It is equivalent to the existence of a permutation a of a vertex set in G such that if an edge xy belongs to E(G), then a(x)cr(y) does not belong to E(G). In 2002 Garcia et al. have shown that a non-star tree T is planary packable into a complete graph Kn. In this paper we show that for any packable cycle Cn except of the case n = 5 and n=7 there exists a planar packing into Kn. We also generalize this result to certain classes of unicyclic graphs.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
673--679
Opis fizyczny
Bibliogr. 7 poz., rys.
Twórcy
autor
- University of Science and Technology AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland, forys@galaxy.uci.agh.edu.pl
Bibliografia
- [1] D. Burns, S. Schuster, Every (p, p−2) graph is contained in its complement, J. Graph Theory 1 (1977), 277-279.
- [2] R. J. Faudree, C. C. Rousseau, R. H. Schelp, S. Schuster, Embedding graphs in their complements, Czechoslovak Math. J. 31 (1981), 53-62.
- [3] A. Garcia, C. Hernando, F. Hurtado, M. Noy, J. Tehel, Packing trees into planar graphs, J. Graph Theory 40, (2002), 172-181.
- [4] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271-283.
- [5] Oswald Veblen, Theory on plane curves in non-metrical analysis situs, Trans. Amer. Math. Soc. 6 (1905), 83-98.
- [6] M. Woźniak, Packing of graphs, Dissertationes Math. 362 (1997), 1-78.
- [7] M. Woźniak, Packing two copies of a tree into a planar graph, Opuscula Math. 23 (2003), 95-97.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-PWA5-0027-0001