zbMATH — the first resource for mathematics

On certain induced subgraphs of Paley graphs. (English) Zbl 1389.05077
Summary: Since the advent of Ramsey theory in the 1930’s, Paley graphs have played an important role in the determination of lower bounds for diagonal Ramsey numbers due to their randomness. The construction of Paley graphs (whose vertices are identified with a finite field \(\mathbb F_q\)) leads to several natural induced subgraphs worth considering. In this paper, we consider the subgraphs induced on the squares \(\mathbb F^{\times 2}_q\) and the subgraphs induced on \(\mathbb F^{\times}_q - \mathbb F^{\times 2}_q\). We describe their basic properties, demonstrate their utility in simplifying the determination of the clique/independence numbers for Paley graphs, and address the determination of their diameters.
05C30 Enumeration in graph theory
11T24 Other character sums and Gauss sums
05C12 Distance in graphs
05C55 Generalized Ramsey theory
05D10 Ramsey theory
Full Text: DOI