Hostname: page-component-8448b6f56d-t5pn6 Total loading time: 0 Render date: 2024-04-18T14:56:19.762Z Has data issue: false hasContentIssue false
  • English
  • Français

RAMSEY NUMBERS FOR TREES

Part of: Graph theory

Published online by Cambridge University Press:  07 February 2012

ZHI-HONG SUN
ZHI-HONG SUN*
Affiliation:
School of Mathematical Sciences, Huaiyin Normal University, Huaian, Jiangsu 223001, PR China (email: zhihongsun@yahoo.com)
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.

For n≥5, let T′n denote the unique tree on n vertices with Δ(T′n)=n−2, and let T*n=(V,E) be the tree on n vertices with V ={v0,v1,…,vn−1} and E={v0v1,…,v0vn−3,vn−3vn−2,vn−2vn−1}. In this paper, we evaluate the Ramsey numbers r(Gm,T′n) and r(Gm,T*n) , where Gm is a connected graph of order m. As examples, for n≥8 we have r(T′n,T*n)=r(T*n,T*n)=2n−5 , for n>m≥7 we have r(K1,m−1,T*n)=m+n−3 or m+n−4 according to whether m−1∣n−3 or m−1∤n−3 , and for m≥7 and n≥(m−3)2 +2 we have r(T*m,T*n)=m+n−3 or m+n−4 according to whether m−1∣n−3 or m−1∤n−3 .

Keywords

Ramsey numbertreeTurán’s problem

MSC classification

Secondary: 05C35: Extremal problems
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 86 , Issue 1 , August 2012 , pp. 164 - 176
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2012

References

[1]Burr, S. A., ‘Generalized Ramsey theory for graphs—a survey’, in: Graphs and Combinatorics, Lecture Notes in Mathematics, 406 (eds. Bari, R.A. and Harary, F.) (Springer, Berlin–New York, 1974), pp. 52–75.CrossRefGoogle Scholar
[2]Burr, S. A. and Roberts, J. A., ‘On Ramsey numbers for stars’, Util. Math. 4 (1973), 217–220.Google Scholar
[3]Erdős, P. and Gallai, T., ‘On maximal paths and circuits in graphs’, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356.CrossRefGoogle Scholar
[4]Fan, G. H. and Sun, L. L., ‘The Erdős–Sós conjecture for spiders’, Discrete Math. 307 (2007), 3055–3062.CrossRefGoogle Scholar
[5]Faudree, R. J. and Schelp, R. H., ‘Path Ramsey numbers in multicolorings’, J. Combin. Theory Ser. B 19 (1975), 150–160.CrossRefGoogle Scholar
[6]Guo, Y. B. and Volkmann, L., ‘Tree-Ramsey numbers’, Aust. J. Combin. 11 (1995), 169–175.Google Scholar
[7]Hua, L. K., Introduction to Number Theory (Springer, Berlin, 1982).Google Scholar
[8]Radziszowski, S. P., ‘Small Ramsey numbers’, Dynamic Surveys of Electronic J. Combinatorics (2011), DS1.13, 84 pp.CrossRefGoogle Scholar
[9]Sidorenko, A. F., ‘Asymptotic solution for a new class of forbidden r-graphs’, Combinatorica 9 (1989), 207–215.CrossRefGoogle Scholar
[10]Sun, Z. H. and Wang, L. L., ‘Turán’s problem for trees’, J. Combin. Number Theory 3 (2011), 51–69.Google Scholar
[11]Woźniak, M., ‘On the Erdős–Sós conjecture’, J. Graph Theory 21 (1996), 229–234.3.0.CO;2-E>CrossRefGoogle Scholar