On path-quasar Ramsey numbers

ArticleOriginal scientific text

Title

Authors ,

Let

G_{1}

and

G_{2}

be two given graphs. The Ramsey number

R (G_{1}, G_{2})

is the least integer

r

such that for every graph

G

on

r

vertices, either

G

contains a

G_{1}

or

\overset{―}{G}

contains a

G_{2}

. Parsons gave a recursive formula to determine the values of

R (P_{n}, K_{1, m})

, where

P_{n}

is a path on

n

vertices and

K_{1, m}

is a star on

m + 1

vertices. In this note, we study the Ramsey numbers

R (P_{n}, K_{1} \lor F_{m})

, where

F_{m}

is a linear forest on

m

vertices. We determine the exact values of

R (P_{n}, K_{1} \lor F_{m})

for the cases

m \leq n

and

m \geq 2 n

, and for the case that

F_{m}

has no odd component. Moreover, we give a lower bound and an upper bound for the case

n + 1 \leq m \leq 2 n - 1

and

F_{m}

has at least one odd component.

Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.
Chen, Y., Zhang, Y., Zhang, K., The Ramsey numbers of paths versus wheels, Discrete Math. 290 (1) (2005), 85–87.
Dirac, G. A., Some theorems on abstract graphs, Proc. London. Math. Soc. 2 (1952), 69–81.
Faudree, R. J., Lawrence, S. L., Parsons, T. D., Schelp, R. H., Path-cycle Ramsey numbers, Discrete Math. 10 (2) (1974), 269–277.
Graham, R. L., Rothschild, B. L., Spencer, J. H., Ramsey Theory, Second Edition, John Wiley & Sons Inc., New York, 1990.
Li, B., Ning, B., The Ramsey numbers of paths versus wheels: a complete solution, Electron. J. Combin. 21 (4) (2014), #P4.41.
Parsons, T. D., Path-star Ramsey numbers, J. Combin. Theory, Ser. B 17 (1) (1974), 51–58.
Rousseau, C. C., Sheehan, J., A class of Ramsey problems involving trees, J. London Math. Soc. 2 (3) (1978), 392–396.
Salman, A. N. M., Broersma, H. J., Path-fan Ramsey numbers, Discrete Applied Math. 154 (9) (2006), 1429–1436.
Salman, A. N. M., Broersma, H. J., Path-kipas Ramsey numbers, Discrete Applied Math. 155 (14) (2007), 1878–1884.
Zhang, Y., On Ramsey numbers of short paths versus large wheels, Ars Combin. 89 (2008), 11–20.