On the restricted size Ramsey number involving a path P 3

Denny Riama Silaban, Edy Tri Baskoro, Saladin Uttunggadewa

Research output: Contribution to journalArticle

Abstract

For any pair of graphs G and H, both the size Ramsey number r(G, H) and the restricted size Ramsey number r (G, H) are bounded above by the size of the complete graph with order equals to the Ramsey number r(G, H), and bounded below by e(G) + e(H) − 1. Moreover, trivially, r(G, H) ≤ r (G, H). When introducing the size Ramsey number for graph, Erdös et al. (1978) asked two questions; (1) Do there exist graphs G and H such that r(G, H) attains the upper bound? and (2) Do there exist graphs G and H such that r(G, H) is significantly less than the upper bound? In this paper we consider the restricted size Ramsey number r (G, H). We answer both questions above for r (G, H) when G = P 3 and H is a connected graph.

Original languageEnglish
Pages (from-to)741-755
Number of pages15
JournalDiscussiones Mathematicae - Graph Theory
Volume39
Issue number2
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • Connected graph
  • Path
  • Restricted size ramsey number
  • Star

Fingerprint Dive into the research topics of 'On the restricted size Ramsey number involving a path P <sub>3</sub>'. Together they form a unique fingerprint.

  • Cite this