27 Settembre, 2016 11:00 in punto

Sezione di Geometria, Algebra e loro applicazioni

Graph decompositions via integer compositions

Emanuele Brugnoli, Università di Palermo

Aula seminari III piano

A composition of a positive integer n is defined as a way of writing n as an ordered sum of positive integers (parts). The study of compositions has a long and rich history. The earliest publication on this subject is by Percy Alexander MacMahon in 1893, entitled Memoir on the Theory of Compositions of a Number and started with the words ``Compositions are merely partitions in which the order of occurrence of the parts is essential.'' MacMahon derived a number of results, for example the total number of compositions and the number of compositions with a given number of parts, using generating functions.

Since the second half of 20th century, several groups of authors developed new research directions studying compositions restricted in some way, as also certain characteristics of these compositions.

In this talk, the strict connection between integer compositions and graph decompositions into Hamiltonian cycles is shown. Denoting, as usual, with K_v the complete graph on v vertices, a Hamiltonian cycle system of odd order v (briefly HCS(v)) is a set of Hamiltonian cycles of K_v whose edges partition the edge-set of K_v. The earliest example of a HCS(2n+1) is attributed to Walecki; its vertex-set is V_{2n+1} := Z_{2n} U { ? } and it consists of all cycles belonging to the orbit of the starter cycle

( ?, 0, 1, -1, 2, -2, …, i, -i, …, n-1, -(n-1), n )

under the natural action of Z_{2n} on V_{2n+1}.

By means of a slight modification of the HCS(4n+1) of Walecki, we obtain 2^n pairwise distinct HCS(4n+1) and we enumerate them up to isomorphism proving that this result can be achieved by counting the inequivalent compositions of n under the action of D_n, the dihedral group of order 2n.

This seminar is organized within the PRIN 2012 Research project «Geometric Structures, Combinatorics and their Applications» Grant Registration number 2012XZE22K, funded by MIUR - Project coordinator Prof.ssa Norma Zagaglia