×

zbMATH — the first resource for mathematics

Paths in graphs. (English) Zbl 0997.05049
The maximum number \(p_s(m)\) of \(s\)-length paths in graphs with \(m\) edges is investigated. If \(6\leq {k\choose 2}\leq m<{{k+1}\choose{2}}\) then \(p_3(m)\leq 2m(m-k)(k-2)/k\) with equality if \(m={k\choose 2}\) and \(K_k\) is considered (or, if \(m=6\), there is another graph). For \(s>3\) odd, \(p_s(m)\sim 2^{{s-1}\over{2}}m^{{s+1}\over{2}}\) is established. For \(l\geq 2\), \(p_{2l}(m)=c_lm^{l+1}+O(m^{l+{{2}\over{3}}})\) with explicitly calculated \(c_l>0\). The proof of the main result of Z. Füredi [Stud. Sci. Math. Hung. 27, 403–407 (1992; Zbl 0695.05026)] is also sketched.

MSC:
05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI