A remark on star-C4 and wheel-C4 Ramsey numbers
Abstract
Given two graphs G1 and G2, the Ramsey number R(G1;G2)
is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote a cycle of order n, Wn a wheel of order n+1 and Sn a star of order n. In this paper, it is shown that R(Wn;C4) = R(Sn+1;C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1;C4), we establish the best possible general upper bound for R(Wn;C4) and determine some exact values for R(Wn;C4).
is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote a cycle of order n, Wn a wheel of order n+1 and Sn a star of order n. In this paper, it is shown that R(Wn;C4) = R(Sn+1;C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1;C4), we establish the best possible general upper bound for R(Wn;C4) and determine some exact values for R(Wn;C4).
Keywords
Ramsey number; star; wheel; quadrilateral; 4-cycle
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2014.2.2.3
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.