On Ramsey numbers for paths versus wheels

Research output: Book/ReportReportOther research output

46 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},W_{m})$, where $P_{n}$ is a path on $n$ vertices and $W_{m}$ is the graph obtained from a cycle on $m$ vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of $R(P_{n},W_{m})$ for the following values of $n$ and $m$: $n=1,2,3$ or $5$ and $m\geq 3$; $n=4$ and $m=3,4,5$ or $7$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); odd $n\ge7$ and $m=2n-2$ or $m=2n$ or $m\geq (n-3)^2$; odd $n\geq 9$ and $q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5$. Moreover, we give nontrivial lower bounds and upper bounds for $R(P_{n},W_{m})$ for the other values of $m$ and $n$.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2004

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.1742
ISSN (Print)0169-2690

Keywords

  • MSC-05C55
  • IR-65926
  • EWI-3562
  • MSC-05D10

Cite this

Salman, M., & Broersma, H. J. (2004). On Ramsey numbers for paths versus wheels. Enschede: University of Twente, Department of Applied Mathematics.
Salman, M. ; Broersma, Haitze J. / On Ramsey numbers for paths versus wheels. Enschede : University of Twente, Department of Applied Mathematics, 2004.
@book{def7d19dd53a40ce83054c11c7d2819d,
title = "On Ramsey numbers for paths versus wheels",
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},W_{m})$, where $P_{n}$ is a path on $n$ vertices and $W_{m}$ is the graph obtained from a cycle on $m$ vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of $R(P_{n},W_{m})$ for the following values of $n$ and $m$: $n=1,2,3$ or $5$ and $m\geq 3$; $n=4$ and $m=3,4,5$ or $7$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); odd $n\ge7$ and $m=2n-2$ or $m=2n$ or $m\geq (n-3)^2$; odd $n\geq 9$ and $q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5$. Moreover, we give nontrivial lower bounds and upper bounds for $R(P_{n},W_{m})$ for the other values of $m$ and $n$.",
keywords = "MSC-05C55, IR-65926, EWI-3562, MSC-05D10",
author = "M. Salman and Broersma, {Haitze J.}",
note = "Imported from MEMORANDA",
year = "2004",
language = "Undefined",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1742",

}

Salman, M & Broersma, HJ 2004, On Ramsey numbers for paths versus wheels. University of Twente, Department of Applied Mathematics, Enschede.

On Ramsey numbers for paths versus wheels. / Salman, M.; Broersma, Haitze J.

Enschede : University of Twente, Department of Applied Mathematics, 2004.

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - On Ramsey numbers for paths versus wheels

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},W_{m})$, where $P_{n}$ is a path on $n$ vertices and $W_{m}$ is the graph obtained from a cycle on $m$ vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of $R(P_{n},W_{m})$ for the following values of $n$ and $m$: $n=1,2,3$ or $5$ and $m\geq 3$; $n=4$ and $m=3,4,5$ or $7$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); odd $n\ge7$ and $m=2n-2$ or $m=2n$ or $m\geq (n-3)^2$; odd $n\geq 9$ and $q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5$. Moreover, we give nontrivial lower bounds and upper bounds for $R(P_{n},W_{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},W_{m})$, where $P_{n}$ is a path on $n$ vertices and $W_{m}$ is the graph obtained from a cycle on $m$ vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of $R(P_{n},W_{m})$ for the following values of $n$ and $m$: $n=1,2,3$ or $5$ and $m\geq 3$; $n=4$ and $m=3,4,5$ or $7$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); odd $n\ge7$ and $m=2n-2$ or $m=2n$ or $m\geq (n-3)^2$; odd $n\geq 9$ and $q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5$. Moreover, we give nontrivial lower bounds and upper bounds for $R(P_{n},W_{m})$ for the other values of $m$ and $n$.

KW - MSC-05C55

KW - IR-65926

KW - EWI-3562

KW - MSC-05D10

M3 - Report

BT - On Ramsey numbers for paths versus wheels

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Salman M, Broersma HJ. On Ramsey numbers for paths versus wheels. Enschede: University of Twente, Department of Applied Mathematics, 2004.