A nearly sharp lower bound on the length of the longest trail in a graph on n vertices and average degree k is given provided the graph is dense enough (k ≥ 12.5).
@article{bwmeta1.element.doi-10_2478_s11533-013-0285-x,
author = {Vajk Sz\'ecsi},
title = {On the minimal length of the longest trail in a fixed edge-density graph},
journal = {Open Mathematics},
volume = {11},
year = {2013},
pages = {1831-1837},
zbl = {1277.05089},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0285-x}
}
Vajk Szécsi. On the minimal length of the longest trail in a fixed edge-density graph. Open Mathematics, Tome 11 (2013) pp. 1831-1837. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-013-0285-x/
[1] Catlin P.A., Super-Eulerian graphs: a survey, J. Graph Theory, 1992, 16(2), 177–196 http://dx.doi.org/10.1002/jgt.3190160209[Crossref]
[2] Erdős P., Gallai T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 1959, 10(3–4), 337–356 http://dx.doi.org/10.1007/BF02024498[Crossref] | Zbl 0090.39401
[3] Faudree R.J., Schelp R.H., Path connected graphs, Acta Math. Acad. Sci. Hungar., 1974, 25(3–4), 313–319 http://dx.doi.org/10.1007/BF01886090[Crossref] | Zbl 0294.05119