### On the Ramsey number of 4-cycle versus wheel

#### 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

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

#### 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.

### Refbacks

• There are currently no refbacks.

ISSN: 2541-2205