{
  "id": "2205.03965",
  "version": "v1",
  "published": "2022-05-08T22:48:00.000Z",
  "updated": "2022-05-08T22:48:00.000Z",
  "title": "Connected size Ramsey numbers of matchings versus a small path or cycle",
  "authors": [
    "Sha Wang",
    "Ruyu Song",
    "Yixin Zhang",
    "Yanbo Zhang"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given two graphs $G_1, G_2$, the connected size Ramsey number ${\\hat{r}}_c(G_1,G_2)$ is defined to be the minimum number of edges of a connected graph $G$, such that for any red-blue edge colouring of $G$, there is either a red copy of $G_1$ or a blue copy of $G_2$. Concentrating on ${\\hat{r}}_c(nK_2,G_2)$ where $nK_2$ is a matching, we generalise and improve two previous results as follows. Vito, Nabila, Safitri, and Silaban obtained the exact values of ${\\hat{r}}_c(nK_2,P_3)$ for $n=2,3,4$. We determine its exact values for all positive integers $n$. Rahadjeng, Baskoro, and Assiyatun proved that ${\\hat{r}}_c(nK_2,C_4)\\le 5n-1$ for $n\\ge 4$. We improve the upper bound from $5n-1$ to $\\lfloor (9n-1)/2 \\rfloor$. In addition, we show a result which has the same flavour and has exact values: ${\\hat{r}}_c(nK_2,C_3)=4n-1$ for all positive integers $n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-05-08T22:48:00.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "connected size ramsey number",
      "small path",
      "exact values",
      "positive integers",
      "blue copy"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}