### A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph

*Zbigniew Lonc, Paweł Naroski*

#### Abstract

By an Euler walk in a 3-uniform hypergraph H
we mean an alternating sequence
v

_{0},e_{1},v_{1},e_{2},v_{2},…,v_{m-1},e_{m},v_{m}of vertices and edges in H such that each edge of H appears in this sequence exactly once and v_{i-1},v_{i}∈e_{i}, v_{i-1}¬=v_{i}, for every i=1,2,…,m. This concept is a natural extension of the graph theoretic notion of an Euler walk to the case of 3-uniform hypergraphs. We say that a 3-uniform hypergraph H is*strongly connected*if it has no isolated vertices and for each two edges e and f in H there is a sequence of edges starting with e and ending with f such that each two consecutive edges in this sequence have two vertices in common. In this paper we give an algorithm that constructs an Euler walk in a strongly connected 3-uniform hypergraph (it is known that such a walk in such a hypergraph always exists). The algorithm runs in time O(m), where m is the number of edges in the input hypergraph.Full Text: PDF PostScript