On tours that contain all edges of a hypergraph

Zbigniew Lonc ; Paweł Naroski

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

Let $H$ be a $k$-uniform hypergraph, $k\geqslant 2$. By an Euler tour in $H$ we mean an alternating sequence $v_0,e_1,v_1,e_2,v_2,\ldots,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,\ldots,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_{odd}(H)|\leqslant (k-2)|E(H)|$, where $V_{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.

Détail

DOI : 10.37236/416

Classification : 05C65, 05C45
Mots-clés : uniform hypergraphs, Euler tours, Euler walks