On tours that contain all edges of a hypergraph
type: Item
instance of: scholarly article
title: On tours that contain all edges of a hypergraph
zbMATH Open document ID: 1204.05064
author: Zbigniew Lonc
author: Paweł Naroski
published in: The Electronic Journal of Combinatorics
publication date: 2010-12-16T00:00:00Z
full work available at URL: https://eudml.org/doc/230726
full work available at URL: v17i1r144.html
review text: 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.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5827393
zbMATH Keywords: uniform hypergraphs
zbMATH Keywords: Euler tours
zbMATH Keywords: Euler walks
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5827393