×

Spanning Euler tours and spanning Euler families in hypergraphs with particular vertex cuts. (English) Zbl 1393.05192

Summary: An Euler tour in a hypergraph is a closed walk that traverses each edge of the hypergraph exactly once, while an Euler family, first defined by A. Bahmanian and M. Šajna [Electron. J. Comb. 24, No. 3, Research Paper P3.30, 12 p. (2017; Zbl 1369.05153); “Eulerian properties of hypergraphs”, Preprint, arXiv:1608.01040], is a family of closed walks that jointly traverse each edge exactly once and cannot be concatenated. In this paper, we study the notions of a spanning Euler tour and a spanning Euler family, that is, an Euler tour (family) that also traverses each vertex of the hypergraph at least once. We examine necessary and sufficient conditions for a hypergraph to admit a spanning Euler family, most notably when the hypergraph possesses a vertex cut consisting of vertices of degree two. Moreover, we characterise hypergraphs with a vertex cut of cardinality at most two that admit a spanning Euler tour (family). This result enables us to reduce the problem of existence of a spanning Euler tour (which is NP-complete), as well as the problem of a spanning Euler family, to smaller hypergraphs.

MSC:

05C65 Hypergraphs
05C45 Eulerian and Hamiltonian graphs
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 1369.05153

References:

[1] Bahmanian, M. A.; Šajna, M., Eulerian properties of hypergraphs, (2015)
[2] Bahmanian, M. A.; Šajna, M., Connection and separation in hypergraphs, Theory Appl. Graphs, 2, 2, (2015), Art. 5, 24 pp · Zbl 1416.05197
[3] Bahmanian, M. A.; Šajna, M., Quasi-Eulerian hypergraphs, Electron. J. Combin., 24, (2017), # P3.30, 12 pp · Zbl 1369.05153
[4] Bondy, J. A.; Murty, U. S.R., (Graph Theory, Graduate Texts in Mathematics, vol. 244, (2008), Springer New York) · Zbl 1134.05001
[5] Lonc, Z.; Naroski, P., On tours that contain all edges of a hypergraph, Electron. J. Combin, 17, (2010), # R144, 31 pp · Zbl 1204.05064
[6] Lovász, L., The factorization of graphs II, Acta Math. Acad. Sci. Hungar., 23, 223-246, (1972) · Zbl 0247.05155
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.