Graphs with the \(n\)-e.c. adjacency property constructed from affine planes (Q2470461)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs with the \(n\)-e.c. adjacency property constructed from affine planes |
scientific article |
Statements
Graphs with the \(n\)-e.c. adjacency property constructed from affine planes (English)
0 references
14 February 2008
0 references
For a positive integer \(n\), a graph is \(n\)-existentially closed or \(n\)-e.c., if for each \(n\)-subset \(S\) of vertices, and each subset \(T\) of \(S\), there is a vertex not in \(S\) joined to each of the vertices of \(T\) and to no vertex in \(S\backslash T\). New examples of graphs with the \(n\)-e.c. adjacency property are given. Few explicit families of \(n\)-e.c. graphs are known, despite the fact that almost all finite graphs are \(n\)-e.c. The examples provided here are collinearity graphs of certain partial planes derived from affine planes of even order. Probabilistic and geometric techniques are used to construct new examples of \(n\)-e.c. graphs from partial planes for all \(n\), and geometric techniques to give infinitely many new explicit examples if \(n=3\). A new construction is proposed, using switching, of an exponential number of non-isomorphic \(n\)-e.c. graphs for certain orders.
0 references
graph
0 references
geometry
0 references
adjacency property
0 references
n-e.c. graph
0 references
affine plane
0 references
switching
0 references