DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

Z. Luo

Zhidan Luo

School of Mathematics and Statistics, Hainan University

email: luodan@hainanu.edu.cn

0009-0005-6195-147X

Title:

Star-critical Ramsey numbers and regular Ramsey numbers for stars

PDF

Source:

Discussiones Mathematicae Graph Theory 45(2) (2025) 755-762

Received: 2023-12-29 , Revised: 2024-06-15 , Accepted: 2024-06-15 , Available online: 2024-06-27 , https://doi.org/10.7151/dmgt.2550

Abstract:

Let $G$ be a graph, $H$ be a subgraph of $G$, and let $G- H$ be the graph obtained from $G$ by removing a copy of $H$. Let $K_{1, n}$ be the star on $n+ 1$ vertices. Let $t\geq 2$ be an integer and $H_{1}, \dots, H_{t}$ and $H$ be graphs, and let $H\rightarrow (H_{1}, \dots, H_{t})$ denote that every $t$ coloring of $E(H)$ yields a monochromatic copy of $H_{i}$ in color $i$ for some $i\in [t]$. The Ramsey number $r(H_{1}, \dots, H_{t})$ is the minimum integer $N$ such that $K_{N}\rightarrow (H_{1}, \dots, H_{t})$. The star-critical Ramsey number $r_{*}(H_{1}, \dots, H_{t})$ is the minimum integer $k$ such that $K_{N}- K_{1, N- 1- k}\rightarrow (H_{1}, \dots, H_{t})$ where $N= r(H_{1}, \dots, H_{t})$. Let $rr(H_{1}, \dots, H_{t})$ be the regular Ramsey number for $H_{1}, \dots, H_{t}$, which is the minimum integer $r$ such that if $G$ is an $r$-regular graph on $r(H_{1}, \dots, H_{t})$ vertices, then $G\rightarrow (H_{1}, \dots, H_{t})$. Let $m_{1}, \dots, m_{t}$ be integers larger than one, exactly $k$ of which are even. In this paper, we prove that if $k\geq 2$ is even, then $r_{*}(K_{1, m_{1}}, \dots, K_{1, m_{t}})= \sum_{i= 1}^{t} m_{i}- t+ 1- \frac{k}{2}$ which disproves a conjecture of Budden and DeJonge in 2022. Furthermore, we prove that $$ rr(K_{1, m_{1}}, \dots, K_{1, m_{t}})= \begin{cases} \sum_{i= 1}^{t} m_{i}- t, & \text{$k\geq 2$ is even},\\ \sum_{i= 1}^{t} m_{i}- t+ 1, & otherwise. \end{cases} $$

Keywords:

star-critical Ramsey numbers, regular Ramsey numbers, stars

References:

  1. B. Bollobás, Extremal Graph Theory, Reprint of the 1978 original (Dover Publications, Inc., Mineola, New York, 2004).
  2. M.R. Budden and E. DeJonge, Multicolor star-critical Ramsey numbers and Ramsey-good graphs, Electron. J. Graph Theory Appl. EJGTA 10 (2022) 51–66.
    https://doi.org/10.5614/ejgta.2022.10.1.4
  3. S. Burr and J. Roberts, On Ramsey numbers for stars, Util. Math. 4 (1973) 217–220.
  4. F. Harary, Graph Theory (Addison-Wesley Publishing Company, Inc., New York, 1969).
  5. F. Harary, Recent results on generalized Ramsey theory for graphs, in: Graph Theory and Applications, Y. Alavi, D.R. Lick and A.T. White (Ed(s)), Lecture Notes in Math. 303, (Springer, Berlin, Heidelberg, 1972) 125–138.
    https://doi.org/10.1007/BFb0067364
  6. J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011) 328–334.
    https://doi.org/10.1016/j.dam.2010.11.007
  7. E. Lucas, Récréations Mathématiques, vol. 2 (Gautheir–Villars, Paris, 1892).
  8. R.H. Schelp, Some Ramsey-Turán type problems and related questions, Discrete Math. 312 (2012) 2158–2161.
    https://doi.org/10.1016/j.disc.2011.09.015

Close