TY - JOUR

T1 - Restricted size Ramsey number for path of order three versus graph of order five

AU - Silaban, Denny Riama

AU - Baskoro, Edy Tri

AU - Uttunggadewa, Saladin

PY - 2017

Y1 - 2017

N2 - Let G and H be simple graphs. The Ramsey number r(G,H) for a pair of graphs G and H is the smallest number r such that any red-blue coloring of the edges of Kr contains a red subgraph G or a blue subgraph H. The size Ramsey number ř(G,H) for a pair of graphs G and H is the smallest number ř such that there exists a graph F with size ř satisfying the property that any red-blue coloring of the edges of F contains a red subgraph G or a blue subgraph H. Additionally, if the order of F in the size Ramsey number equals r(G,H), then it is called the restricted size Ramsey number. In 1983, Harary and Miller started to find the (restricted) size Ramsey numbers for pairs of small graphs with orders at most four. Faudree and Sheehan (1983) continued Harary and Miller's works and summarized the complete results on the (restricted) size Ramsey numbers for pairs of small graphs with orders at most four. In 1998, Lortz and Mengenser gave both the size Ramsey numbers and the restricted size Ramsey numbers for pairs of small forests with orders at most five. To continue their works, we investigate the restricted size Ramsey numbers for a path of order three versus any connected graph of order five.

AB - Let G and H be simple graphs. The Ramsey number r(G,H) for a pair of graphs G and H is the smallest number r such that any red-blue coloring of the edges of Kr contains a red subgraph G or a blue subgraph H. The size Ramsey number ř(G,H) for a pair of graphs G and H is the smallest number ř such that there exists a graph F with size ř satisfying the property that any red-blue coloring of the edges of F contains a red subgraph G or a blue subgraph H. Additionally, if the order of F in the size Ramsey number equals r(G,H), then it is called the restricted size Ramsey number. In 1983, Harary and Miller started to find the (restricted) size Ramsey numbers for pairs of small graphs with orders at most four. Faudree and Sheehan (1983) continued Harary and Miller's works and summarized the complete results on the (restricted) size Ramsey numbers for pairs of small graphs with orders at most four. In 1998, Lortz and Mengenser gave both the size Ramsey numbers and the restricted size Ramsey numbers for pairs of small forests with orders at most five. To continue their works, we investigate the restricted size Ramsey numbers for a path of order three versus any connected graph of order five.

KW - Connected graph

KW - Path

KW - Restricted size Ramsey number

UR - http://www.scopus.com/inward/record.url?scp=85020490267&partnerID=8YFLogxK

U2 - 10.5614/ejgta.2017.5.1.15

DO - 10.5614/ejgta.2017.5.1.15

M3 - Article

AN - SCOPUS:85020490267

VL - 5

SP - 155

EP - 162

JO - Electronic Journal of Graph Theory and Applications

JF - Electronic Journal of Graph Theory and Applications

SN - 2338-2287

IS - 1

ER -