HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Eulerian and Hamiltonian Directed Hypergraphs

Guillaume Ducoffe 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Let $H=(\mathcal{V},\mathcal{E})$ be a directed hypergraph, sometimes called a dihypergraph. Each vertex $v\in{\mathcal{V}}$ is incident to some hyperarcs in $\mathcal{E}$. Conversely, each hyperarc $E\in{\mathcal{E}}$ is incident to some vertices in $\mathcal{V}$. $H$ is Eulerian if there is a circuit $C$ such that each hyperarc $E\in{\mathcal{E}}$ appears exactly once in $C$. Similarly, $H$ is Hamiltonian if there is a circuit $C^{'}$ such that every vertex $v\in{\mathcal{V}}$ appears exactly once in $C^{'}$. We show that both of the problems are NP-complete. Some necessary conditions for a dihypergraph to be Eulerian are presented. We exhibit some families of hypergraphs for which those are sufficient conditions. We also generalize a part of the properties of the Eulerian digraphs to the uniform and regular directed hypergraphs. Stronger generalizations of \textit{Eulerianicity} to dihypergraphs are also studied. Finally, we show that the de Bruijn and Kautz dihypergraphs are Eulerian and Hamiltonian in most cases. We also study some properties of their bipartite representation digraph.
Document type :
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download

Contributor : Guillaume Ducoffe Connect in order to contact the contributor
Submitted on : Friday, April 13, 2012 - 8:04:45 AM
Last modification on : Friday, February 4, 2022 - 3:11:30 AM
Long-term archiving on: : Wednesday, December 14, 2016 - 9:42:39 PM


Files produced by the author(s)


  • HAL Id : hal-00674655, version 3



Guillaume Ducoffe. Eulerian and Hamiltonian Directed Hypergraphs. [Research Report] RR-7893, INRIA. 2012, pp.55. ⟨hal-00674655v3⟩



Record views


Files downloads