Quasi-Eulerian hypergraphs (Q2401411): Difference between revisions

Summary: We generalize the notion of an Euler tour in a graph in the following way. An Euler family in a hypergraph is a family of closed walks that jointly traverse each edge of the hypergraph exactly once. An Euler tour thus corresponds to an Euler family with a single component. We provide necessary and sufficient conditions for the existence of an Euler family in an arbitrary hypergraph, and in particular, we show that every 3-uniform hypergraph without cut edges admits an Euler family. Finally, we show that the problem of existence of an Euler family is polynomial on the class of all hypergraphs. { }This work complements existing results on rank-1 universal cycles and 1-overlap cycles in triple systems, as well as recent results by \textit{Z. Lonc} and \textit{P. Naroski} [Electron. J. Comb. 17, No. 1, Research Paper R144, 31 p. (2010; Zbl 1204.05064)], who showed that the problem of existence of an Euler tour in a hypergraph is NP-complete.