Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-00674655
Contributor : Guillaume Ducoffe <>
Submitted on : Friday, April 13, 2012 - 8:04:45 AM
Last modification on : Monday, October 12, 2020 - 10:30:26 AM
Long-term archiving on: : Wednesday, December 14, 2016 - 9:42:39 PM

File

euler01032011.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00674655, version 3

Collections

Citation

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

Share

Metrics

Record views

511

Files downloads

355