\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Zbigniew Lonc and Pawe\l\ Naroski }
%
%
\medskip
\noindent
%
%
{\bf On Tours that contain all Edges of a Hypergraph}
%
%
\vskip 5mm
\noindent
%
%
%
%
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}\not=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.
\end{document}