Planar packing of cycles and unicyclic graphs

• Autorzy: Gorlich A.
• Języki publikacji: EN

Abstrakty

EN

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

EN

planar graph; tree; cycle

PL

graf płaski; grafy

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2009
• Tom: Vol. 42, nr 4
• Strony: 673--679
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Gorlich A.

• University of Science and Technology AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland,

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.