Decompositions of nearly complete digraphs into t isomorphic parts

Mariusz Meszka; Zdzisław Skupień

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 3, page 563-572
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Mariusz Meszka, and Zdzisław Skupień. "Decompositions of nearly complete digraphs into t isomorphic parts." Discussiones Mathematicae Graph Theory 29.3 (2009): 563-572. <http://eudml.org/doc/270948>.

@article{MariuszMeszka2009,
abstract = {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.},
author = {Mariusz Meszka, Zdzisław Skupień},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {decomposition; cyclically 1-generated; remainder; surplus; universal part},
language = {eng},
number = {3},
pages = {563-572},
title = {Decompositions of nearly complete digraphs into t isomorphic parts},
url = {http://eudml.org/doc/270948},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Mariusz Meszka
AU - Zdzisław Skupień
TI - Decompositions of nearly complete digraphs into t isomorphic parts
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 563
EP - 572
AB - 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.
LA - eng
KW - decomposition; cyclically 1-generated; remainder; surplus; universal part
UR - http://eudml.org/doc/270948
ER -

References

top
  1. [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. Zbl1022.05061
  2. [2] C. Berge, Graphs and Hypergraphs (North-Holland, 1973). 
  3. [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. Zbl0344.05123
  4. [4] J. Bosák, Decompositions of Graphs (Dordrecht, Kluwer, 1990, [Slovak:] Bratislava, Veda, 1986). 
  5. [5] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & Hall, 1996). Zbl0890.05001
  6. [6] A. Fortuna and Z. Skupień, On nearly third parts of complete digraphs and complete 2-graphs, manuscript. Zbl1276.05077
  7. [7] F. Harary and R.W. Robinson, Isomorphic factorizations X: Unsolved problems, J. Graph Theory 9 (1985) 67-86, doi: 10.1002/jgt.3190090105. Zbl0617.05051
  8. [8] F. Harary, R.W. Robinson and N.C. Wormald, Isomorphic factorisation V: Directed graphs, Mathematika 25 (1978) 279-285, doi: 10.1112/S0025579300009529. Zbl0387.05015
  9. [9] A. Kedzior and Z. Skupień, Universal sixth parts of a complete graph exist, manuscript. 
  10. [10] E. Lucas, Récréations Mathématiques, vol. II (Paris, Gauthier-Villars, 1883). 
  11. [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. Zbl0924.05052
  12. [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. Zbl0940.05054
  13. [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. Zbl1084.05054
  14. [14] M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5 (1981) 45-53, doi: 10.1002/jgt.3190050103. Zbl0448.05031
  15. [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. Zbl0116.15001
  16. [16] Z. Skupień, The complete graph t-packings and t-coverings, Graphs Combin. 9 (1993) 353-363, doi: 10.1007/BF02988322. Zbl0795.05116
  17. [17] Z. Skupień, Clique parts independent of remainders, Discuss. Math. Graph Theory 22 (2002) 361, doi: 10.7151/dmgt.1181. Zbl1028.05077
  18. [18] Z. Skupień, Universal fractional parts of a complete graph, manuscript. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.