Lai's conditions for spanning and dominating closed trails
Summary: A graph is supereulerian if it has a spanning closed trail. For an integer \(r\), let \(\mathcal Q_0(r)\) be the family of 3-edge-connected nonsupereulerian graphs of order at most \(r\). For a graph \(G\), define \(\delta_L(G)=\min\{\max\{d(u), d(v) \}|\,\,\text{for any}\,\, uv\in E(G)\}\). For a given integer \(p\geq 2\) and a given real number \(\epsilon\), a graph \(G\) of order \(n\) is said to satisfy a Lai's condition if \(\delta_L(G)\geq \frac{n}{p}-\epsilon\). In this paper, we show that if \(G\) is a 3-edge-connected graph of order \(n\) with \(\delta_L(G)\geq \frac{n}{p}-\epsilon\), then there is an integer \(N(p, \epsilon)\) such that when \(n> N(p,\epsilon)\), \(G\) is supereulerian if and only if \(G\) is not a graph obtained from a graph \(G_p\) in the finite family \(\mathcal Q_0(3p-5)\) by replacing some vertices in \(G_p\) with nontrivial graphs. Results on the best possible Lai's conditions for Hamiltonian line graphs of 3-edge-connected graphs or 3-edge-connected supereulerian graphs are given, which are improvements of the results in [\textit{Z.-H. Chen}, J. Graph Theory 42, No. 4, 308--319 (2003; Zbl 1018.05059)] and in [\textit{X. Li}, Discrete Math. 310, No. 17--18, 2455--2459 (2010; Zbl 1230.05189)].
- A note on graphs spanned by Eulerian graphs
- A reduction method to find spanning Eulerian subgraphs
- Collapsible graphs and matchings
- Contractions of graphs with no spanning Eulerian subgraphs
- Eulerian subgraphs containing given vertices and hamiltonian line graphs
- Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs
- Fan-type conditions for spanning Eulerian subgraphs
- Graph theory with applications
- Graphs without spanning closed trails
- Hamiltonian line graphs
- scientific article; zbMATH DE number 4055653 (Why is no real title available?)
- scientific article; zbMATH DE number 6604940 (Why is no real title available?)
- On 3-edge-connected supereulerian graphs in graph family \(C(l,k)\)
- On a closure concept in claw-free graphs
- On circuits and pancyclic line graphs
- On dominating and spanning circuits in graphs
- On Eulerian and Hamiltonian Graphs and Line Graphs
- On Spanning and Dominating Circuits in Graphs
- Properties of Catlin's reduced graphs and supereulerian graphs
- Supereulerian graphs and the Petersen graph
- Supereulerian graphs, independent sets, and degree-sum conditions
- The spanning subgraphs of eulerian graphs
- The traveling salesman problem on cubic and subcubic graphs
This page was built for publication: Lai's conditions for spanning and dominating closed trails
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2260637)
