Existentially closed critical Cayley graphs

A graph is called \(t\)-existentially closed (\(t\)-e.c.) if it satisfies the following adjacency property: for every \(t\)-element subset \(A\) of the vertices, and for every subset \(B ⊆ A\), there exists a vertex \(x ∈ A\) that is adjacent to all vertices in \(B\) and to none of the vertices in \(A B\). A \(t\)-e.c. graph is critical if removing any single vertex results in a graph that is no longer \(t\)-e.c. This paper investigates \(2\)-e.c. critical Cayley graphs and vertex-transitive graphs, providing explicit constructions of \(2\)-e.c. critical Cayley graphs on cyclic groups. It is shown that a \(2\)-e.c. critical Cayley graph (as well as vertex-transitive graphs) of order \(n\) exists if and only if \(n ≥ 9\) and \(n ∉ \{10, 11, 14\}\). Additionally, this paper examines the numbers of \(2\)-e.c. (critical) vertex-transitive graphs among all vertex-transitive graphs for small orders, and presents detailed observations on some \(2\)-e.c. and \(3\)-e.c. vertex-transitive graphs.