Path-fan Ramsey numbers

Research output: Book/ReportReportOther research output

36 Downloads (Pure)

Abstract

For two given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $p$ such that for every graph $F$ on $p$ vertices the following holds: either $F$ contains $G$ as a subgraph or the complement of $F$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_{n},F_{m})$, where $P_{n}$ is a path on $n$ vertices and $F_{m}$ is the graph obtained from $m$ disjoint triangles by identifying precisely one vertex of every triangle ($F_{m}$ is the join of $K_{1}$ and $mK_{2}$). We determine exact values for $R(P_{n},F_{m})$ for the following values of $n$ and $m$: $n=1,2$ or $3$ and $m\geq 2$; $n\geq 4$ and $2\leq m\leq (n+1)/2$; $n\geq7$ and $m=n-1$ or $m=n$; $n\geq 8$ and $(k\cdot n-2k+1)/2\leq m\leq (k\cdot n-k+2)/2$ with $3\leq k\leq n-5$; $n=4,5$ or $6$ and $m\geq n-1$; $n\geq 7$ and $m\geq (n-3)^2/2$. We conjecture that $R(P_{n},F_{m}) \leq 2m+n-3$ for the other values of $m$ and $n$.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2003

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherUniversity of Twente, Department of Applied Mathematics
No.1703
ISSN (Print)0169-2690

Fingerprint

Ramsey number
Path
Subgraph
Triangle
Graph in graph theory
Join
Disjoint
Complement
Integer
Vertex of a graph
Fan

Keywords

  • MSC-05C55
  • EWI-3523
  • IR-65888
  • MSC-05D10

Cite this

Salman, M., & Broersma, H. J. (2003). Path-fan Ramsey numbers. (Memorandum / Department of Applied Mathematics; No. 1703). Enschede: University of Twente, Department of Applied Mathematics.
Salman, M. ; Broersma, Haitze J. / Path-fan Ramsey numbers. Enschede : University of Twente, Department of Applied Mathematics, 2003. (Memorandum / Department of Applied Mathematics; 1703).
@book{844a72ca8db64636a548fa56dcbcaafc,
title = "Path-fan Ramsey numbers",
abstract = "For two given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $p$ such that for every graph $F$ on $p$ vertices the following holds: either $F$ contains $G$ as a subgraph or the complement of $F$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_{n},F_{m})$, where $P_{n}$ is a path on $n$ vertices and $F_{m}$ is the graph obtained from $m$ disjoint triangles by identifying precisely one vertex of every triangle ($F_{m}$ is the join of $K_{1}$ and $mK_{2}$). We determine exact values for $R(P_{n},F_{m})$ for the following values of $n$ and $m$: $n=1,2$ or $3$ and $m\geq 2$; $n\geq 4$ and $2\leq m\leq (n+1)/2$; $n\geq7$ and $m=n-1$ or $m=n$; $n\geq 8$ and $(k\cdot n-2k+1)/2\leq m\leq (k\cdot n-k+2)/2$ with $3\leq k\leq n-5$; $n=4,5$ or $6$ and $m\geq n-1$; $n\geq 7$ and $m\geq (n-3)^2/2$. We conjecture that $R(P_{n},F_{m}) \leq 2m+n-3$ for the other values of $m$ and $n$.",
keywords = "MSC-05C55, EWI-3523, IR-65888, MSC-05D10",
author = "M. Salman and Broersma, {Haitze J.}",
note = "Imported from MEMORANDA",
year = "2003",
language = "English",
series = "Memorandum / Department of Applied Mathematics",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1703",

}

Salman, M & Broersma, HJ 2003, Path-fan Ramsey numbers. Memorandum / Department of Applied Mathematics, no. 1703, University of Twente, Department of Applied Mathematics, Enschede.

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

Enschede : University of Twente, Department of Applied Mathematics, 2003. (Memorandum / Department of Applied Mathematics; No. 1703).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Path-fan Ramsey numbers

AU - Salman, M.

AU - Broersma, Haitze J.

N1 - Imported from MEMORANDA

PY - 2003

Y1 - 2003

N2 - For two given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $p$ such that for every graph $F$ on $p$ vertices the following holds: either $F$ contains $G$ as a subgraph or the complement of $F$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_{n},F_{m})$, where $P_{n}$ is a path on $n$ vertices and $F_{m}$ is the graph obtained from $m$ disjoint triangles by identifying precisely one vertex of every triangle ($F_{m}$ is the join of $K_{1}$ and $mK_{2}$). We determine exact values for $R(P_{n},F_{m})$ for the following values of $n$ and $m$: $n=1,2$ or $3$ and $m\geq 2$; $n\geq 4$ and $2\leq m\leq (n+1)/2$; $n\geq7$ and $m=n-1$ or $m=n$; $n\geq 8$ and $(k\cdot n-2k+1)/2\leq m\leq (k\cdot n-k+2)/2$ with $3\leq k\leq n-5$; $n=4,5$ or $6$ and $m\geq n-1$; $n\geq 7$ and $m\geq (n-3)^2/2$. We conjecture that $R(P_{n},F_{m}) \leq 2m+n-3$ for the other values of $m$ and $n$.

AB - For two given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $p$ such that for every graph $F$ on $p$ vertices the following holds: either $F$ contains $G$ as a subgraph or the complement of $F$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_{n},F_{m})$, where $P_{n}$ is a path on $n$ vertices and $F_{m}$ is the graph obtained from $m$ disjoint triangles by identifying precisely one vertex of every triangle ($F_{m}$ is the join of $K_{1}$ and $mK_{2}$). We determine exact values for $R(P_{n},F_{m})$ for the following values of $n$ and $m$: $n=1,2$ or $3$ and $m\geq 2$; $n\geq 4$ and $2\leq m\leq (n+1)/2$; $n\geq7$ and $m=n-1$ or $m=n$; $n\geq 8$ and $(k\cdot n-2k+1)/2\leq m\leq (k\cdot n-k+2)/2$ with $3\leq k\leq n-5$; $n=4,5$ or $6$ and $m\geq n-1$; $n\geq 7$ and $m\geq (n-3)^2/2$. We conjecture that $R(P_{n},F_{m}) \leq 2m+n-3$ for the other values of $m$ and $n$.

KW - MSC-05C55

KW - EWI-3523

KW - IR-65888

KW - MSC-05D10

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

BT - Path-fan Ramsey numbers

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Salman M, Broersma HJ. Path-fan Ramsey numbers. Enschede: University of Twente, Department of Applied Mathematics, 2003. (Memorandum / Department of Applied Mathematics; 1703).