×

Path-kipas Ramsey numbers. (English) Zbl 1128.05037

The Ramsey number \(R(P_n, K_1 + P_m)\) is determined for various ranges of \(n\) and \(m\), where \(P_n\) is a path with \(n\) vertices, and \(K_1 + P_m\) is the graph obtained from a path \(P_m\) by adding an additional vertex that is adjacent to all of the vertices of the path. For example, it is shown that \(R(P_n, K_1 + P_m) = 2n - 1\) for \(n \geq 4\), \(m\) even, and \(4 \leq m \leq n + 1\). This result follows a previous paper of the authors on \(R(P_n, W_m)\), where \(W_m\) is the wheel with \(m + 1\) vertices. On certain intervals bounds are given of which the following is an example. If \(n \geq 6\) and \(m\) is even with \(n + 2 \leq m \leq \lfloor n/3 \rfloor\), then \(m + \lfloor (3n)/2 \rfloor - 2 \geq R(P_n, K_1 + P_m) \geq 2n - 1\). Many small order Ramsey numbers are determined for the pair \((P_n, K_1 + P_m)\).

MSC:

05C55 Generalized Ramsey theory
05D10 Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burr, S. A.; Erdös, P.; Faudree, R. J.; Rousseau, C. C.; Schelp, R. H., Ramsey numbers for the pair sparse graph-path or cycle, Trans. Amer. Math. Soc., 269, 2, 501-512 (1982) · Zbl 0543.05047
[2] Faudree, R. J.; Lawrence, S. L.; Parsons, T. D.; Schelp, R. H., Path-cycle Ramsey numbers, Discrete Math., 10, 269-277 (1974) · Zbl 0293.05120
[3] Faudree, R. J.; Schelp, R. H.; Simonovits, M., On some Ramsey type problems connected with paths, cycles and trees, Ars Combin., 29A, 97-106 (1990) · Zbl 0708.05040
[4] Geréncser, L.; Gyárfás, A., On Ramsey-type problems, Annales Universitatis Scientiarum Budapestinensis, Eötvös Sect. Math., 10, 167-170 (1967) · Zbl 0163.45502
[5] Häggkvist, R., On the path-complete bipartite Ramsey numbers, Discrete Math., 75, 243-245 (1989) · Zbl 0692.05046
[6] Parsons, T. D., The Ramsey numbers \(r(P_m, K_n)\), Discrete Math., 6, 159-162 (1973) · Zbl 0279.05123
[7] Parsons, T. D., Path-star Ramsey numbers, J. Combin. Theory Ser. B, 17, 51-58 (1974) · Zbl 0282.05110
[8] A.N.M. Salman, H.J. Broersma, On Ramsey numbers for paths versus wheels, Discrete Math. 307 (2007) 975-982.; A.N.M. Salman, H.J. Broersma, On Ramsey numbers for paths versus wheels, Discrete Math. 307 (2007) 975-982. · Zbl 1115.05060
[9] Salman, A. N.M.; Broersma, H. J., Path-fan Ramsey numbers, Discrete Appl. Math., 154, 1429-1436 (2006) · Zbl 1093.05043
[10] Surahmat, A.; Baskoro, E. T., On the Ramsey number of a path or a star versus \(W_4\) or \(W_5\), (Proceedings of the 12th Australasian Workshop on Combinatorial Algorithms (2001)), 174-178
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.