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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references