Lai's conditions for spanning and dominating closed trails (Q2260637)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lai's conditions for spanning and dominating closed trails |
scientific article |
Statements
Lai's conditions for spanning and dominating closed trails (English)
0 references
11 March 2015
0 references
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)].
0 references
spanning and dominating closed trails
0 references
Hamiltonian line graphs
0 references
collapsible graphs
0 references