Decompositions of complete symmetric directed graphs into the oriented heptagons

The complete symmetric directed graph of order v , denoted by K∗ v , is the directed graph on v vertices that contains both arcs (x, y) and (y, x) for each pair of distinct vertices x and y . For a given directed graph D, the set of all v for which K∗ v admits a D-decomposition is called the spectrum of D-decomposition. There are 10 nonisomorphic orientations of a 7-cycle (heptagon). In this paper, we completely settled the spectrum problem for each of the oriented heptagons.

PDF

___

[1] Abel RJ, Bennett FE, Greig M. PBD-Closure. In: Colbourn CJ, Dinitz JH (editors). Handbook of Combinatorial Designs. Boca Raton, FL, USA: Chapman and Hall/CRC Press, 2007, pp. 246-254.
[2] Adams P, Bunge RC, Dulowski J, El-Zanati SI et al. The λ-fold spectrum problem for the orientations of the 6-cycle. preprint.
[3] Alspach B, Gavlas H. Cycle decompositions of Kn and Kn − I . Journal of Combinatorial Theory, Series B 2001; 81 (1): 77-99.
[4] Alspach B, Gavlas H, Šajna M, Verrall H. Cycle decompositions IV: complete directed graphs and fixed length directed cycles. Journal of Combinatorial Theory, Series A 2003; 103 (1): 165-208.
[5] Alspach B, Heinrich K, Varma BN. Decompositions of complete symmetric digraphs into the oriented pentagons. Journal of the Australian Mathematical Society 1979; 28 (3): 353-361.
[6] Bermond JC. An application of the solution of Kirkman’s schoolgirl problem: the decomposition of the symmetric oriented complete graph into 3-circuits. Discrete Mathematics 1974; 8 (4): 301-304.
[7] Colbourn CJ, Dinitz JH. Handbook of Combinatorial Designs. Boca Raton, FL, USA: Chapman/CRC Press, 2007.
[8] Ge G. Group divisible designs. In: Colbourn CJ, Dinitz JH (editors). Handbook of Combinatorial Designs. Boca Raton, FL, USA: Chapman and Hall/CRC Press, 2007, pp. 255-260.
[9] Harary F, Wallis WD, Heinrich K. Decomposition of complete symmetric digraph into the four oriented quadrilaterals. In: Holton DA, Seberry J (editors). Lecture Notes in Mathematics, Vol. 686. Berlin, Germany: Springer-Verlag, 1978, pp. 165-173.
[10] Hung SH, Mendelsohn NS. Directed triple systems. Journal of Combinatorial Theory, Series B 1973; 14 (3): 310-318.
[11] Liu J. A generalization of the Oberwolfach problem and Ct -factorizations of complete equipartite graphs. Journal of Combinatorial Designs 2000; 8 (1): 42-49.
[12] Liu J. The equipartite Oberwolfach Problem with uniform tables. Journal of Combinatorial Theory, Series A 2003; 101 (1): 20-34.
[13] Mendelsohn NS. A generalisation of Steiner triple systems. In: Atkin AO, Birch BJ (editors). Computers in number theory. New York, USA: Academic Press, 1971, pp. 323-339.
[14] Schönheim J. Partition of the edges of the directed complete graph into 4-cycles. Discrete Mathematics 1975; 11 (1): 67-70.