Paper detail

Eulerian properties of hypergraphs

In this paper we study three substructures in hypergraphs that generalize the notion of an Euler tour in a graph. A flag-traversing tour of a hypergraph corresponds to an Euler tour of its incidence graph, hence complete characterization of hypergraphs with an Euler tour follows from Euler's Theorem. An Euler tour is a closed walk that traverses each edge of the hypergraph exactly once; and an Euler family is a family of closed walks that cannot be concatenated and that jointly traverse each edge of the hypergraph exactly once. Lonc and Naroski have shown that the problem of existence of an Euler tour is NP-complete even on a very restricted subclass of 3-uniform hypergraphs, while we show that the problem of existence of an Euler family is polynomial on the class of all hypergraphs. Furthermore, we examine the necessary conditions for a hypergraph to admit an Euler family (Euler tour, respectively); we show that while these necessary conditions are sufficient for connected graphs, they are not sufficient for general hypergraphs. On the other hand, we exhibit a new class of hypergraphs for which these necessary conditions are also sufficient, extending a result by Lonc and Naroski. We give a partial characterization of hypergraphs with an Euler family (Euler tour, respectively) in terms of the intersection graph of the hypergraph, and a complete (but not easy to verify) characterization in terms of the incidence graph. For hypergraphs with an Euler family, we give a complete verifiable characterization using a theorem of Lovász, and then show that every 3-uniform hypergraph without cut edges admits an Euler family. Finally, we show that a hypergraph admits an Euler family if and only if it can be decomposed into cycles, and exhibit a relationship between 2-factors in a hypergraph and eulerian properties of its dual.