Universal third parts of any complete 2-graph and none of DK5

• Autorzy: Fortuna A. , Skupień Z.
• Języki publikacji: EN

Abstrakty

EN

It is shown that there is no digraph F which could decompose the complete digraph on 5 vertices minus any 2-arc remainder into three parts isomorphic to F for each choice of the remainder. On the other hand, for each n ≥ 3 there is a universal third part F of the complete 2-graph 2Kn on n vertices, i.e., for each edge subset R of size [formula] mod 3, there is an F-decomposition of 2Kn−R. Using an exhaustive computer-aided search, we find all, exactly six, mutually nonisomorphic universal third parts of the 5-vertex 2-graph. Nevertheless, none of their orientations is a universal third part of the corresponding complete digraph.

Słowa kluczowe

EN

decomposition; remainder; universal parts; isomorphic parts

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2013
• Tom: Vol. 33, no. 4
• Strony: 685--696
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Fortuna A.

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

autor

Skupień Z.

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

Bibliografia

• [1] J. Bosák, Decompositions of Graphs, Kluwer Acad. Publ., Dordrecht, 1990.
• [2] V. Chungphaisan, Conditions for sequences to be r-graphic, Discrete Math. 7 (1974), 31–39.
• [3] R. Diestel, Graph Theory, Springer, New York, 2005.
• [4] F. Harary, R.W. Robinson, N. Wormald, Isomorphic factorisations. I: Complete graphs, Trans. Amer. Math. Soc. 242 (1978), 243–260.
• [5] F. Harary, R.W. Robinson, N. Wormald, Isomorphic factorisations. V: Directed graphs, Mathematika 25 (1978), 279–285.
• [6] A. Kedzior, Z. Skupien, Universal sixth parts of a complete graph exist, manuscript (2009).
• [7] E. Lucas, Récréations Mathématiques, vol. II, Gauthier-Villars, Paris, 1883.
• [8] M. Meszka, Generating third parts of nearly complete digraphs [in Polish], Jagiellonian University, MSc thesis (1994).
• [9] M. Meszka, Z. Skupien, Self-converse and oriented graphs among the third parts of nearly complete digraphs, Combinatorica 18 (1998), 413–424.
• [10] M. Meszka, Z. Skupien, On some third parts of nearly complete digraphs, Discrete Math. 212 (2000), 129–139.
• [11] M. Meszka, Z. Skupien, Decompositions of nearly complete digraphs into t isomorphic parts, Discuss. Math. Graph Theory 29 (2009), 563–572.
• [12] R.C. Read, On the number of self-complementary graphs and digraphs, J. London Math. Soc. 38 (1963), 99–104.
• [13] J. Schönheim, A. Bialostocki, Decomposition of Kn into subgraphs of prescribed type, Arch. Math. 31 (1978), 105–112.
• [14] Z. Skupien, The complete graph t-packings and t-coverings, Graphs Comb. 9 (1993), 353–363.
• [15] Z. Skupien, Clique parts independent of remainders, Discuss. Math. Graph Theory 22 (2002), 361.
• [16] Z. Skupien, Universal parts, either large or with small remainder, of a complete graph, manuscript (2004).
• [17] Z. Skupien, Matchings and near-matchings among universal graphical fractions, manuscript (2013).
• [18] D.B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 2001.