Back to Search
Start Over
Polarity graphs and Ramsey numbers for [formula omitted] versus stars.
- Source :
-
Discrete Mathematics . Apr2017, Vol. 340 Issue 4, p655-660. 6p. - Publication Year :
- 2017
-
Abstract
- For two given graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that for any graph of order N , either G contains a copy of G 1 or its complement contains a copy of G 2 . Let C m be a cycle of length m and K 1 , n a star of order n + 1 . Parsons (1975) shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 and if n is the square of a prime power, then the equality holds. In this paper, by discussing the properties of polarity graphs whose vertices are points in the projective planes over Galois fields, we prove that R ( C 4 , K 1 , q 2 − t ) = q 2 + q − ( t − 1 ) if q is an odd prime power, 1 ≤ t ≤ 2 ⌈ q 4 ⌉ and t ≠ 2 ⌈ q 4 ⌉ − 1 , which extends a result on R ( C 4 , K 1 , q 2 − t ) obtained by Parsons (1976). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 340
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 121784159
- Full Text :
- https://doi.org/10.1016/j.disc.2016.12.005