On tours that contain all edges of a hypergraph (Q612925)

Summary: Let \(H\) be a \(k\)-uniform hypergraph, \(k\geq 2\). By an Euler tour in \(H\) we mean an alternating sequence \(v_0,e_1,v_1,e_2,v_2,\dots,v_{m-1},e_m,v_m=v_0\) of vertices and edges in \(H\) such that each edge of \(H\) appears in this sequence exactly once and \(v_{i-1},v_i\in e_i\), \(v_{i-1}\neq v_i\), for every \(i=1,2,\dots,m\). This is an obvious generalization of the graph theoretic concept of an Euler tour. A straightforward necessary condition for existence of an Euler tour in a \(k\)-uniform hypergraph is \(|V_{\text{odd}}(H)|\leq (k-2)|E(H)|\), where \(V_{\text{odd}}(H)\) is the set of vertices of odd degrees in \(H\) and \(E(H)\) is the set of edges in \(H\). In this paper we show that this condition is also sufficient for hypergraphs of a broad class of \(k\)-uniform hypergraphs, that we call strongly connected hypergraphs. This result reduces to the Euler theorem on existence of Euler tours, when \(k=2\), i.e. for graphs, and is quite simple to prove for \(k>3\). Therefore, we concentrate on the most interesting case of \(k=3\). In this case we further consider the problem of existence of an Euler tour in a certain class of 3-uniform hypergraphs containing the class of strongly connected hypergraphs as a proper subclass. For hypergraphs in this class we give a sufficient condition for existence of an Euler tour and prove intractability (NP-completeness) of the problem in this class in general.