Cubic and quadruple Paley graphs with the \(n\)-e.c. property (Q860460): Difference between revisions

A graph \(G\) is \(n\)-existentially closed or \(n\)-e.c. if for any two disjoint subsets \(A\) and \(B\) of vertices of \(G\) with \(\left| A\cup B\right| =n \), there is a vertex \(u\notin A\cup B\) that is adjacent to every vertex of \(A \) but not adjacent to any vertex of \(B\). It is well known that almost all graphs are \(n\)-e.c. Example of \(n\)-e.c. graphs are the Paley graphs which are defined as follows. Let \(q\equiv 1\pmod4\) be a prime power. The vertices of Paley graphs are the elements of the finite field \(\mathbb{F}_{q} \). Two vertices \(a\) and \(b\) are adjacent if and only if their difference is a quadratic residue. Previous results established that Paley graphs are \(n\)-e.c. for sufficiently large \(q\). By using higher order residues on finite fields other classes of graphs are generated which are called cubic and quadruple Paley graphs. It is shown that cubic Paley graphs are \(n\)-e.c. whenever \(q\geq n^{2}2^{4n-2}\) and quadruple Paley graphs are \(n\)-e.c. whenever \(q\geq 9n^{2}6^{2n-2}\). Similar adjacency properties for quadruple Paley digraphs are investigated also.