Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 792.05076
Autor: Erdös, Paul; Faudree, Ralph J.; Schelp, R.H.; Simonovits, M.
Title: An extremal result for paths. (In English)
Source: Capobianco, Michael F. (ed.) et al., Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986. New York: New York Academy of Sciences, Ann. N. Y. Acad. Sci. 576, 155-162 (1989).
Review: One of the best known extremal results involving paths is the following one proved more than 25 years ago.
Theorem [P. Erd\H os and T. Gallai, Acta Math. Acad. Sci. Hung. 10, 337-356 (1959; Zbl 090.39401)]: A graph Gm on m vertices with at least [m(k-1)+1]/2 edges contains a path Pk+1 on k+1 vertices. Furthermore, when m = kt the graph tKk contains the maximal number of edges in an m vertex graph with no Pk+1 and is the unique such graph.
There are many other results in the literature that use that a graph with many edges or with high-degree vertices has a long path.
The problem we address here is of a similar nature. Let m,n and k be fixed positive integers with m > n \geq k. We wish to determine the minimum value l such that each graph on m vertices with l vertices of degree at least n contains a Pk+1.
A plausible minimum value for l is suggested by the following graph. Let m = t(n+1)+r, 0 \leq r < n+1, with k < 2n+1. Then the graph consisting of t vertex disjoint copies of H = \overline Kn+1-\lfloor (k-1)/2 \rfloor+K\lfloor (k-1)/2 \rfloor contains t \lfloor(k- 1)/2\rfloor vertices of degree n and no Pk+1. When k is even and r+\lfloor (k-1)/2 \rfloor \geq n, the number of vertices of degree \geq n in this graph can be increased by 1 to t \lfloor (k-1)/2 \rfloor+1 without forcing the graphs to contain a Pk+1. Simply take one of the vertices of degree \lfloor (k-1)/2 \rfloor and make it adjacent to the r vertices in no copy of H. Thus we have the following conjecture:
Let m,n, and k be fixed positive integers with m > n \geq k and set \delta = 2 when k is even and \delta = 1 when k is odd. If Gm is a graph on m vertices and at least l = \lfloor (k-1)/2 \rfloor \lfloor m/(n+1) \rfloor+\delta vertices of degree \geq n, then Gm contains a Pk+1.
Although we do not prove the conjectured result, we do show that the value of l given in the conjecture is ``essentially'' correct. Much attention is given to the special case when n+1 \leq m \leq 2n+1. In this case we show that approximately k/2 vertices of degree \geq n is enough to guarantee that Gm contains a Pk+1. Unfortunately, even for this interval of values we are not able to prove the exact statement of the conjecture.
Classif.: * 05C35 Extremal problems (graph theory)
05C38 Paths and cycles
Keywords: extremal results; paths; maximal number
Citations: Zbl 090.394
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag