On hamiltonian line graphs of hypergraphs
- 14 January 2022
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 100 (3) , 489-503
Abstract
A graph is supereulerian if it has a spanning eulerian subgraph. Harary and Nash‐Williams in 1968 proved that the line graph of a graph is hamiltonian if and only if has a dominating eulerian subgraph, Jaeger in 1979 showed that every 4‐edge‐connected graph is supereulerian, and Catlin in 1988 proved that every graph with two edge‐disjoint spanning trees is a contractible configuration for supereulerianicity. Utilizing the notion of partition‐connectedness of hypergraphs introduced by Frank, Király, and Kriesell in 2003, we generalize the above‐mentioned results of Harary and Nash‐Williams, of Jaeger and of Catlin to hypergraphs by characterizing hypergraphs whose line graphs are hamiltonian, and showing that every 2‐partition‐connected hypergraph is a contractible configuration for supereulerianicity.Keywords
Funding Information
- Simons Foundation
This publication has 11 references indexed in Scilit:
- Graph Theory2008
- On decomposing a hypergraph into k connected sub-hypergraphsDiscrete Applied Mathematics, 2003
- On a Closure Concept in Claw-Free GraphsJournal of Combinatorial Theory, Series B, 1997
- Hamiltonicity for K1, r‐free graphsJournal of Graph Theory, 1995
- Supereulerian graphs: A surveyJournal of Graph Theory, 1992
- A reduction method to find spanning Eulerian subgraphsJournal of Graph Theory, 1988
- Reflections on graph theoryJournal of Graph Theory, 1986
- Hamiltonian results in K1,3‐free graphsJournal of Graph Theory, 1984
- A Note on Sub‐Eulerian GraphsJournal of Graph Theory, 1979
- On Eulerian and Hamiltonian Graphs and Line GraphsCanadian Mathematical Bulletin, 1965