On the Ramsey number of 4-cycle versus wheel

Enik Noviani, Edy Tri Baskoro

Abstract


For any fixed graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $n$ such that for every graph $F$ on $n$ vertices must contain $G$ or the complement of $F$ contains $H$. The girth of graph $G$ is a length of the shortest cycle. A $k$-regular graph with the girth $g$ is called a $(k,g)$-graph. If the number of of vertices in $(k,g)$-graph is minimized then we call this graph a $(k,g)$-cage. In this paper, we derive the bounds of Ramsey number $R(C_4,W_n)$ for some values of $n$. By modifying $(k, 5)$-graphs, for $k = 7$ or $9$, we construct these corresponding $(C_4,W_n)$-good graphs. 


Keywords


Ramsey number; good graph; order; cycle; wheel; girth

Full Text:

PDF

References


A.J.Hoffman, R.R.Singleton, On the Moore graphs of diameters 2 and 3, IBM J. Res. De- velop. (1960).

J. Dybizban ́ski, T. Dzido, On Some Ramsey Numbers for Quadrilaterals versus Wheels, Graphs and Combinatorics 30 (2014), 573-579.

K.K. Tse, On the Ramsey Tur ́an Number for Quadrilateral, Utilitas Mathematica., 79, (2003) 51-58.

L.K.Jørgensen, Girth 5 Graphs from Relative Difference Sets, Discreate Mathematics, 293, (2005) 177-184.

S.P Radziszowski, Small Ramsey Numbers, Electronic Journal of Combinatorics, http://www.combinatorics.org, DSI, 84 pages.

S.P Radziszowski, K.K.Tse, A computational approach for the Ramsey numbers R(C4, Kn) . Journal of Combinatorial Mathematics and Combinatorial Computing 42 (2002), 195-207.

W. Yali, S. Yongqi, S.P Radziszowski, Wheel and Star-critical Ramsey Numbers for Quadri- lateral, Discrete Applied Mathematics 186 (2015) 260-271.

Y. Zhang, H. Broersma, Y. Chen, A Remark on Star- C4 and Wheel- C4 Ramsey Numbers, Electronic Journal of Graph Theory and Applications 2 (2), (2014) 110-114.




DOI: http://dx.doi.org/10.19184/ijc.2016.1.1.2

Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats