Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
685--696
Opis fizyczny
Bibliogr. 18 poz., rys., tab.
Twórcy
autor
- AGH University of Science and Technology Faculty of Applied Mathematics al. Mickiewicza 30, 30-059 Krakow, Poland
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-6ad389f7-6d22-482d-a529-ef5fd0c72813