Path-kipas Ramsey numbers

Research output: Book/ReportReportProfessional

25 Downloads (Pure)

Abstract

For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_n,\hat{K}_m)$, where $P_n$ is a path on $n$ vertices and $\hat{K}_m$ is the graph obtained from the join of $K_{1}$ and $P_{m}$. We determine the exact values of $R(P_n,\hat{K}_m)$ for the following values of $n$ and $m$: $1\leq n\leq 5$ and $m\geq 3$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); $6\le n\le7$ and $m=2n-2$ or $m\geq 2n$; $n\geq8$ and $m=2n-2$ or $m=2n$ or $(q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5)$ or $m\geq (n-3)^2$; odd $n\geq9$ and $(q\cdot n-3q+1\leq m\leq q\cdot n-2q$ with $3\leq q\leq (n-3)/2)$ or $(q\cdot n-q-n+4\leq m\leq q\cdot n-2q$ with $(n-1)/2\leq q\leq n-4)$. Moreover, we give lower bounds and upper bounds for $R(P_{n},\hat{K}_m)$ for the other values of $m$ and $n$.
Original languageUndefined
Place of PublicationEnschede
PublisherToegepaste Wiskunde
Number of pages11
ISBN (Print)0169-2690
Publication statusPublished - 2004

Publication series

NameMemorandum afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1743
ISSN (Print)0169-2690

Keywords

  • METIS-220232
  • MSC-05D10
  • MSC-05C55
  • EWI-3563
  • IR-65927

Cite this

Salman, M., & Broersma, H. J. (2004). Path-kipas Ramsey numbers. (Memorandum afdeling TW; No. 1743). Enschede: Toegepaste Wiskunde.
Salman, M. ; Broersma, Haitze J. / Path-kipas Ramsey numbers. Enschede : Toegepaste Wiskunde, 2004. 11 p. (Memorandum afdeling TW; 1743).
@book{7b4a5d7704ae48829b72787eab03887d,
title = "Path-kipas Ramsey numbers",
abstract = "For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_n,\hat{K}_m)$, where $P_n$ is a path on $n$ vertices and $\hat{K}_m$ is the graph obtained from the join of $K_{1}$ and $P_{m}$. We determine the exact values of $R(P_n,\hat{K}_m)$ for the following values of $n$ and $m$: $1\leq n\leq 5$ and $m\geq 3$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); $6\le n\le7$ and $m=2n-2$ or $m\geq 2n$; $n\geq8$ and $m=2n-2$ or $m=2n$ or $(q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5)$ or $m\geq (n-3)^2$; odd $n\geq9$ and $(q\cdot n-3q+1\leq m\leq q\cdot n-2q$ with $3\leq q\leq (n-3)/2)$ or $(q\cdot n-q-n+4\leq m\leq q\cdot n-2q$ with $(n-1)/2\leq q\leq n-4)$. Moreover, we give lower bounds and upper bounds for $R(P_{n},\hat{K}_m)$ for the other values of $m$ and $n$.",
keywords = "METIS-220232, MSC-05D10, MSC-05C55, EWI-3563, IR-65927",
author = "M. Salman and Broersma, {Haitze J.}",
note = "Imported from MEMORANDA",
year = "2004",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum afdeling TW",
publisher = "Toegepaste Wiskunde",
number = "1743",

}

Salman, M & Broersma, HJ 2004, Path-kipas Ramsey numbers. Memorandum afdeling TW, no. 1743, Toegepaste Wiskunde, Enschede.

Path-kipas Ramsey numbers. / Salman, M.; Broersma, Haitze J.

Enschede : Toegepaste Wiskunde, 2004. 11 p. (Memorandum afdeling TW; No. 1743).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Path-kipas Ramsey numbers

AU - Salman, M.

AU - Broersma, Haitze J.

N1 - Imported from MEMORANDA

PY - 2004

Y1 - 2004

N2 - For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_n,\hat{K}_m)$, where $P_n$ is a path on $n$ vertices and $\hat{K}_m$ is the graph obtained from the join of $K_{1}$ and $P_{m}$. We determine the exact values of $R(P_n,\hat{K}_m)$ for the following values of $n$ and $m$: $1\leq n\leq 5$ and $m\geq 3$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); $6\le n\le7$ and $m=2n-2$ or $m\geq 2n$; $n\geq8$ and $m=2n-2$ or $m=2n$ or $(q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5)$ or $m\geq (n-3)^2$; odd $n\geq9$ and $(q\cdot n-3q+1\leq m\leq q\cdot n-2q$ with $3\leq q\leq (n-3)/2)$ or $(q\cdot n-q-n+4\leq m\leq q\cdot n-2q$ with $(n-1)/2\leq q\leq n-4)$. Moreover, we give lower bounds and upper bounds for $R(P_{n},\hat{K}_m)$ for the other values of $m$ and $n$.

AB - For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_n,\hat{K}_m)$, where $P_n$ is a path on $n$ vertices and $\hat{K}_m$ is the graph obtained from the join of $K_{1}$ and $P_{m}$. We determine the exact values of $R(P_n,\hat{K}_m)$ for the following values of $n$ and $m$: $1\leq n\leq 5$ and $m\geq 3$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); $6\le n\le7$ and $m=2n-2$ or $m\geq 2n$; $n\geq8$ and $m=2n-2$ or $m=2n$ or $(q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5)$ or $m\geq (n-3)^2$; odd $n\geq9$ and $(q\cdot n-3q+1\leq m\leq q\cdot n-2q$ with $3\leq q\leq (n-3)/2)$ or $(q\cdot n-q-n+4\leq m\leq q\cdot n-2q$ with $(n-1)/2\leq q\leq n-4)$. Moreover, we give lower bounds and upper bounds for $R(P_{n},\hat{K}_m)$ for the other values of $m$ and $n$.

KW - METIS-220232

KW - MSC-05D10

KW - MSC-05C55

KW - EWI-3563

KW - IR-65927

M3 - Report

SN - 0169-2690

T3 - Memorandum afdeling TW

BT - Path-kipas Ramsey numbers

PB - Toegepaste Wiskunde

CY - Enschede

ER -

Salman M, Broersma HJ. Path-kipas Ramsey numbers. Enschede: Toegepaste Wiskunde, 2004. 11 p. (Memorandum afdeling TW; 1743).