Cubic and quadruple Paley graphs with the ne.c. property
Abstract
A graph G is nexistentially closed or ne.c. if for any two disjoint subsets A and B of vertices of G with A ∪ B = n, there is a vertex u /∈A ∪ B that is adjacent to every vertex of A but not adjacent to any vertex of B. It is wellknown that almost all graphs are ne.c. However, few classes of ne.c. graphs have been constructed. A good construction is the Paley graphs which are defined as follows. Let q ≡ 1(mod 4) be a prime power. The vertices of Paley graphs are the elements of the finite field Fq. Two vertices a and b are adjacent if and only if their difference is a quadratic residue. Previous results established that Paley graphs are ne.c. for sufficiently large q. By using higher order residues on finite fields we can generate other classes of graphs which we called cubic and quadruple Paley graphs. We show that cubic Paley graphs are ne.c. whenever q_n224n−2 and quadruple Paley graphs are ne.c. whenever q_9n262n−2.We also investigate a similar adjacency property for quadruple Paley digraphs.
Citation
Source Title
Additional URLs
ISSN
Collection
Related items
Showing items related by title, author, creator and subject.

Ananchuen, Watcharaphong (1993)A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices 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. ...

Ananchuen, Nawarat (1994)Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n  1, G is said to be kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...

Ananchuen, N.; Ananchuen, W.; Caccetta, Louis (2017)A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set ...