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 tourthus 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 Lonc and Naroski, who showed that the problem of existence of an Euler tour in a hypergraph is NP-complete.
@article{10_37236_6361,
author = {Amin Bahmanian and Mateja \v{S}ajna},
title = {Quasi-Eulerian hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {3},
doi = {10.37236/6361},
zbl = {1369.05153},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6361/}
}
TY - JOUR
AU - Amin Bahmanian
AU - Mateja Šajna
TI - Quasi-Eulerian hypergraphs
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/6361/
DO - 10.37236/6361
ID - 10_37236_6361
ER -
