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
Full Text: