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
    0 references
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references