16 Giugno, 2017 14:40 in punto

Sezione di Geometria, Algebra e loro applicazioni

Decompositions of the complete n-partite equipartite multigraph with any minimum leave and minimum excess

Tao Feng, Department of Mathematics, Beijing Jiaotong University, P. R. China

Aula seminari III piano

A decomposition of ?K_n(g) \ L, the complete n-partite equipartite multigraph with a subgraph L (called the leave) removed, into edge disjoint copies of a graph G is called a maximum group divisible packing of ?K_n(g) with G if L contains as few edges as possible. A decomposition of ?K_n(g) ? E, the complete n-partite equipartite multigraph union a graph E (called the excess), into edge disjoint copies of a graph G is called a minimum group divisible covering of ?Kn(g) with G if E contains as few edges as possible.

We continue Billington and Lindner’s work in [1] to examine all possible minimum leaves for maximum group divisible packings of ?Kn(g) with G and all possible excesses for minimum group divisible coverings of ?Kn(g) with G, where G is a triangle K3, or a triangle plus one dangling edge K3 + e, or K4 ? e [2, 3]. When G is K4, the problem is closely related with many other combinatorial con?gurations, such as balanced sampling plans excluding contiguous units, matching divisible designs, etc. We shall show that the obvious divisibility conditions are su?cient for the existence of matching divisible designs with block size four [4].

References

[1] E.J. Billington, C.C. Lindner, Maximum packings of uniform group divisible triple systems, J. Combin. Designs, 4 (1996), 397–404.

[2] X. Hu, Y. Chang, and T. Feng, Group divisible packings and coverings with any minimum leave and minimum excess, Graphs and Combinatorics, 32 (2016), 1423–1446.

[3] Y. Gao, Y. Chang, and T. Feng, Group divisible (K4 ? e)-packings with any minimum leave, arXiv:1705.08787.

[4] P.J. Dukes, T. Feng, A.C.H. Ling, Matching divisible designs with block size four, Discrete Math., 339 (2016), 790–799.