Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 29 | 3 | 563-572

Tytuł artykułu

Decompositions of nearly complete digraphs into t isomorphic parts

Treść / Zawartość

Warianty tytułu

Języki publikacji

EN

Abstrakty

EN
An arc decomposition of the complete digraph 𝒟 Kₙ into t isomorphic subdigraphs is generalized to the case where the numerical divisibility condition is not satisfied. Two sets of nearly tth parts are constructively proved to be nonempty. These are the floor tth class (𝒟 Kₙ-R)/t and the ceiling tth class (𝒟 Kₙ+S)/t, where R and S comprise (possibly copies of) arcs whose number is the smallest possible. The existence of cyclically 1-generated decompositions of 𝒟 Kₙ into cycles $^{→}C_{n-1}$ and into paths $^{→}Pₙ$ is characterized.

Wydawca

Rocznik

Tom

29

Numer

3

Strony

563-572

Opis fizyczny

Daty

wydano
2009
otrzymano
2008-05-08
poprawiono
2008-09-22
zaakceptowano
2008-10-13

Twórcy

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

Bibliografia

  • [1] B. Alspach, H. Gavlas, M. Sajna and H. Verrall, Cycle decopositions IV: complete directed graphs and fixed length directed cycles, J. Combin. Theory (A) 103 (2003) 165-208, doi: 10.1016/S0097-3165(03)00098-0.
  • [2] C. Berge, Graphs and Hypergraphs (North-Holland, 1973).
  • [3] J.C. Bermond and V. Faber, Decomposition of the complete directed graph into k-circuits, J. Combin. Theory (B) 21 (1976) 146-155, doi: 10.1016/0095-8956(76)90055-1.
  • [4] J. Bosák, Decompositions of Graphs (Dordrecht, Kluwer, 1990, [Slovak:] Bratislava, Veda, 1986).
  • [5] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & Hall, 1996).
  • [6] A. Fortuna and Z. Skupień, On nearly third parts of complete digraphs and complete 2-graphs, manuscript.
  • [7] F. Harary and R.W. Robinson, Isomorphic factorizations X: Unsolved problems, J. Graph Theory 9 (1985) 67-86, doi: 10.1002/jgt.3190090105.
  • [8] F. Harary, R.W. Robinson and N.C. Wormald, Isomorphic factorisation V: Directed graphs, Mathematika 25 (1978) 279-285, doi: 10.1112/S0025579300009529.
  • [9] A. Kedzior and Z. Skupień, Universal sixth parts of a complete graph exist, manuscript.
  • [10] E. Lucas, Récréations Mathématiques, vol. II (Paris, Gauthier-Villars, 1883).
  • [11] M. Meszka and Z. Skupień, Self-converse and oriented graphs among the third parts of nearly complete digraphs, Combinatorica 18 (1998) 413-424, doi: 10.1007/PL00009830.
  • [12] M. Meszka and Z. Skupień, On some third parts of nearly complete digraphs, Discrete Math. 212 (2000) 129-139, doi: 10.1016/S0012-365X(99)00214-9.
  • [13] M. Meszka and Z. Skupień, Decompositions of a complete multidigraph into nonhamiltonian paths, J. Graph Theory 51 (2006) 82-91, doi: 10.1002/jgt.20122.
  • [14] M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5 (1981) 45-53, doi: 10.1002/jgt.3190050103.
  • [15] R.C. Read, On the number of self-complementary graphs and digraphs, J. London Math. Soc. 38 (1963) 99-104, doi: 10.1112/jlms/s1-38.1.99.
  • [16] Z. Skupień, The complete graph t-packings and t-coverings, Graphs Combin. 9 (1993) 353-363, doi: 10.1007/BF02988322.
  • [17] Z. Skupień, Clique parts independent of remainders, Discuss. Math. Graph Theory 22 (2002) 361, doi: 10.7151/dmgt.1181.
  • [18] Z. Skupień, Universal fractional parts of a complete graph, manuscript.

Typ dokumentu

Bibliografia

Identyfikatory

Identyfikator YADDA

bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1464
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.