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

# Eulerian and Hamiltonian Directed Hypergraphs

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.
Keywords :
Document type :
Reports
Complete list of metadata

Cited literature [38 references]

https://hal.inria.fr/hal-00674655
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

### File

euler01032011.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00674655, version 3

### Citation

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

Record views