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) |
Keywords:
hypergraph; Euler tour; spanning Euler tour; Euler family; spanning Euler family; vertex cutCitations:
Zbl 1369.05153References:
[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.