Quasi-Eulerian hypergraphs

MaRDI QIDQ2401411zbMATH OpenFDO

Authors Mateja Šajna, M. A. Bahmanian

Publication date 8 September 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\((g,f)\)-factorEuler familyEuler tourEulerian hypergraphhypergraphquasi-Eulerian hypergraph

Mathematics Subject Classification ID

Triple systems (05B07) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Summary: We generalize the notion of an Euler tour in a graph in the following way. An Euler family in a hypergraph is a family of closed walks that jointly traverse each edge of the hypergraph exactly once. An Euler tour thus corresponds to an Euler family with a single component. We provide necessary and sufficient conditions for the existence of an Euler family in an arbitrary hypergraph, and in particular, we show that every 3-uniform hypergraph without cut edges admits an Euler family. Finally, we show that the problem of existence of an Euler family is polynomial on the class of all hypergraphs. { }This work complements existing results on rank-1 universal cycles and 1-overlap cycles in triple systems, as well as recent results by \textit{Z. Lonc} and \textit{P. Naroski} [Electron. J. Comb. 17, No. 1, Research Paper R144, 31 p. (2010; Zbl 1204.05064)], who showed that the problem of existence of an Euler tour in a hypergraph is NP-complete.

Recommendations

• Spanning Euler tours and spanning Euler families in hypergraphs with particular vertex cuts
• Using edge cuts to find Euler tours and Euler families in hypergraphs
• On tours that contain all edges of a hypergraph
• Covering hypergraphs are Eulerian
• Triple systems are Eulerian

Cites work

• 1-overlap cycles for Steiner triple systems
• An algorithmic proof of Tutte's f-factor theorem
• Canonical edge-colourings of locally finite graphs
• Extending edge-colorings of complete hypergraphs into regular colorings
• On tours that contain all edges of a hypergraph
• Ordering block designs. Gray codes, universal cycles and configuration orderings
• Quasi-Eulerian hypergraphs
• Spanning eulerian subgraphs, the splitting lemma, and Petersen's theorem
• The factorization of graphs. II
• Triple systems are Eulerian
• Universal cycles for combinatorial structures

Cited in

(16)

• Quasi-ultrametrics and their \(2\)-ball hypergraphs
• Spanning Euler tours and spanning Euler families in hypergraphs with particular vertex cuts
• Circuit decompositions and shortest circuit coverings of hypergraphs
• Quasi-Eulerian hypergraphs
• Tight Euler tours in uniform hypergraphs -- computational aspects
• Satisfiability thresholds for regular occupation problems
• Triple systems are Eulerian
• A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph
• Covering hypergraphs are Eulerian
• On tours that contain all edges of a hypergraph
• A combinatorial model for lane merging
• Using edge cuts to find Euler tours and Euler families in hypergraphs
• Euler's theorem for regular CW-complexes
• Satisfiability thresholds for regular occupation problems
• -covering k-hypergraphs are quasi-Eulerian
• Spanning Euler tours in hypergraphs

This page was built for publication: Quasi-Eulerian hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401411)