Cubic and quadruple Paley graphs with the n-e.c. property
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 |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 well-known that almost all graphs are n-e.c. However, few classes of n...
| Main Authors: | , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier Science BV
2006
|
| Online Access: | http://www.elsevier.com/wps/find/journaldescription.cws_home/505610/description#description http://hdl.handle.net/20.500.11937/17637 |
| _version_ | 1848749517888815104 |
|---|---|
| author | Ananchuen, Watcharaphong Caccetta, Louis |
| author_facet | Ananchuen, Watcharaphong Caccetta, Louis |
| author_sort | Ananchuen, Watcharaphong |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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 |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 well-known that almost all graphs are n-e.c. However, few classes of n-e.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 n-e.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 n-e.c. whenever q_n224n−2 and quadruple Paley graphs are n-e.c. whenever q_9n262n−2.We also investigate a similar adjacency property for quadruple Paley digraphs. |
| first_indexed | 2025-11-14T07:22:12Z |
| format | Journal Article |
| id | curtin-20.500.11937-17637 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:22:12Z |
| publishDate | 2006 |
| publisher | Elsevier Science BV |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-176372017-05-30T07:59:52Z Cubic and quadruple Paley graphs with the n-e.c. property Ananchuen, Watcharaphong Caccetta, Louis 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 |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 well-known that almost all graphs are n-e.c. However, few classes of n-e.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 n-e.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 n-e.c. whenever q_n224n−2 and quadruple Paley graphs are n-e.c. whenever q_9n262n−2.We also investigate a similar adjacency property for quadruple Paley digraphs. 2006 Journal Article http://hdl.handle.net/20.500.11937/17637 http://www.elsevier.com/wps/find/journaldescription.cws_home/505610/description#description Elsevier Science BV restricted |
| spellingShingle | Ananchuen, Watcharaphong Caccetta, Louis Cubic and quadruple Paley graphs with the n-e.c. property |
| title | Cubic and quadruple Paley graphs with the n-e.c. property |
| title_full | Cubic and quadruple Paley graphs with the n-e.c. property |
| title_fullStr | Cubic and quadruple Paley graphs with the n-e.c. property |
| title_full_unstemmed | Cubic and quadruple Paley graphs with the n-e.c. property |
| title_short | Cubic and quadruple Paley graphs with the n-e.c. property |
| title_sort | cubic and quadruple paley graphs with the n-e.c. property |
| url | http://www.elsevier.com/wps/find/journaldescription.cws_home/505610/description#description http://hdl.handle.net/20.500.11937/17637 |