Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-07T04:47:07.733Z Has data issue: false hasContentIssue false
  • English
  • Français

Turán Numbers of Multiple Paths and Equibipartite Forests

Published online by Cambridge University Press:  12 October 2011

NEAL BUSHAW  and
NATHAN KETTLE
NEAL BUSHAW
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA (e-mail: nobushaw@memphis.edu)
NATHAN KETTLE
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK (e-mail: n.kettle@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The Turán number of a graph H, ex(n, H), is the maximum number of edges in any graph on n vertices which does not contain H as a subgraph. Let Pl denote a path on l vertices, and let k ⋅ Pl denote k vertex-disjoint copies of Pl. We determine ex(n, k ⋅ P3) for n appropriately large, answering in the positive a conjecture of Gorgol. Further, we determine ex(n, k ⋅ Pl) for arbitrary l, and n appropriately large relative to k and l. We provide some background on the famous Erdős–Sós conjecture, and conditional on its truth we determine ex(n, H) when H is an equibipartite forest, for appropriately large n.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 6 , November 2011 , pp. 837 - 853
Copyright
Copyright © Cambridge University Press 2011

References

[1]Balasubramanian, S. and Dobson, E. (2007) On the Erdős–Sós conjecture for graphs with no K 2,s. J. Graph Theory 56 301–310.CrossRefGoogle Scholar
[2]Balister, P. N., Győri, E., Lehel, J. and Schelp, R. H. (2008) Connected graphs without long paths. Discrete Math. 308 4487–4494.CrossRefGoogle Scholar
[3]Bollobás, B. (2002) Modern Graph Theory, Springer.Google Scholar
[4]Brandt, S. and Dobson, E. (1996) The Erdős–Sós conjecture for graphs of girth 5. Discrete Math. 150 411–414.CrossRefGoogle Scholar
[5]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337–356.CrossRefGoogle Scholar
[6]Gorgol, I. (2011) Turán numbers for disjoint copies of graphs. Graphs Combin. 27 661–667.CrossRefGoogle Scholar
[7]Kopylov, G. N. (1977) On maximal paths and cycles in a graph. Soviet Math. Dokl. 18 593–596.Google Scholar
[8]McLennan, A. (2005) The Erdős–Sós conjecture for trees of diameter four. J. Graph Theory 49 291–301.CrossRefGoogle Scholar
[9]Moser, W. and Pach, J. (1993) Recent developments in combinatorial geometry. In New Trends in Discrete and Computational Geometry, Springer, pp. 281–302.CrossRefGoogle Scholar
[10]Saclé, J. F. and Woźniak, M. (1997) The Erdős–Sós conjecture for graphs without C 4. J. Combin. Theory Ser. B 70 367–372.CrossRefGoogle Scholar
[11]Sidorenko, A. (1989) Asymptotic solution for a new class of forbidden r-graphs. Combinatorica 9 207–215.CrossRefGoogle Scholar
[12]Simonovits, M. (1968) A method for solving extremal problems in extremal graph theory. In Theory of Graphs (Erdős, P. and Katona, G., eds), Academic Press, pp. 279–319.Google Scholar
[13]Turán, P. (1941) Egy gráfelméleti szélsőértékfeladatról. Mat. es Fiz. Lapok. 48 436–452.Google Scholar
[14]Turán, P. (1954) On the theory of graphs. Colloquium Math. 3 19–30.CrossRefGoogle Scholar
[15]Woźniak, M. (1996) On the Erdős–Sós conjecture. J. Graph Theory 21 229–234.3.0.CO;2-E>CrossRefGoogle Scholar