Cubic Neighbourhoods in Triple Systems

Abstract

In a triple system of index 3, the multiset of pairs appearing in triples with a fixed element form a cubic multigraph called the neighbourhood of the element. We prove that, with precisely three exceptions, every cubic multigraph appears as an element neighbourhood in a triple system. The proof technique involves establishing the existence of certain path factorizations of cubic graphs. Show more