On the minimal length of the longest trail in a fixed edge-density graph

• Autorzy: Vajk Szécsi
• Języki publikacji: EN

Abstrakty

EN

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).

Słowa kluczowe

EN

Extremal graph theory; Paths; Trails

Kategorie tematyczne

• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2013
• Tom: 11
• Numer: 10
• Strony: 1831-1837

Daty

wydano

2013-10-01

online

2013-07-20

Twórcy

autor

Vajk Szécsi

• Department of Mathematics and its Applications, Central European University, Nádor u. 9, Budapest, 1051, Hungary

Bibliografia

• [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]
• [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]

Identyfikatory

DOI

10.2478/s11533-013-0285-x