On the adjacency properties of generalized Paley graphs
Let \(m\) and \(n\) be nonnegative integers and let \(k\) be a positive integer. A graph \(G\) is said to have property \(P(m,n,k)\) if for any \(m+n\) distinct vertices of \(G\) there are at least \(k\) other vertices, each of which is adjacent to the first \(m\) vertices but not adjacent to any of the latter \(n\) vertices. It is known that almost all graphs have property \(P(m,n,k)\). However, for the case \(m,n\geq 2\), almost no such graphs have been constructed, with the only known examples being Paley graphs, which are defined as follows. For \(q\equiv 1\pmod 4\) a prime power, the Paley graph \(G_q\) of order \(q\) is the graph whose vertices are elements of the finite field \(\mathbb{F}_q\) with two vertices adjacent if and only if their difference is a quadratic residue. By using higher-order residues on finite fields the author generates other classes of graphs which he refers to as genealized Paley graphs. He then shows that, for any \(m\), \(n\) and \(k\), all sufficiently large (order) graphs obtained by taking cubic and quadruple residues have property \(P(m,n,k)\).
- The number of edges on generalizations of Paley graphs
- On a Paley-type graph on \({\mathbb{Z}}_n\)
- On maximal cliques of Cayley graphs over fields
- Generalised Paley graphs with a product structure
- On eigenfunctions and maximal cliques of generalised Paley graphs of square order
- A note on constructing digraphs with prescribed properties
- scientific article; zbMATH DE number 57412 (Why is no real title available?)
- scientific article; zbMATH DE number 166086 (Why is no real title available?)
- On the directions determined by Cartesian products and the clique number of generalized Paley graphs
- Paley-type graphs of order a product of two distinct primes
- The isoperimetric number of a generalized Paley graph
- On the adjacency properties of paley graphs
- Character sums and Ramsey properties of generalized Paley graphs
- scientific article; zbMATH DE number 7700570 (Why is no real title available?)
- On the Paley graph of a quadratic character
- Number of cliques of Paley-type graphs over finite commutative local rings
- Universal graph series, chromatic functions, and their index theory
- Cubic and quadruple Paley graphs with the n-e.c. property
- A generalization of generalized Paley graphs and new lower bounds for \(R(3,q)\)
This page was built for publication: On the adjacency properties of generalized Paley graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2760433)
