On an adjacency property of almost all graphs (Q5937580)

For a positive integer \(n\), a graph \(G\) is \(n\)-existentially closed (briefly, \(n\)-e.c.) if, for every subset \(T\) of any \(n\)-element subset \(S\) of \(V(G)\), there exists a vertex \(v\notin S\) which is adjacent to all vertices in \(T\) and to no vertices in \(S-T\); an \(n\)-e.c. graph \(G\) is \(n\)-e.c. critical if, for each \(x\in V(G)\), \(G-x\) is not \(n\)-e.c.; \(n\)-e.c. graphs were studied in [\textit{L. Caccetta, P. Erdős} and \textit{K. Vijayan}, A property of random graphs, Ars Comb. 19A, 287-294 (1985; Zbl 0572.05036)], where they were called ``graphs with property \(P(n)\).'' The authors observe that the countably infinite graph discovered by Erdős and Rényi [\textit{P. Erdős} and \textit{A. Rényi}, Asymmetric graphs, Acta Math. Acad. Sci. Hung. 14, 295-315 (1963; Zbl 0118.18901)] and called, by Cameron, ``the'' random graph [\textit{P. J. Cameron}, The random graph. Graham, Ronald L. (ed.) et al., The mathematics of Paul Erdős. Vol. II. Berlin: Springer. Algorithms Comb. 14, 333-351 (1997; Zbl 0864.05076)] is \(n\)-e.c. for all \(n\). From the authors' abstract: ``We classify the 1-e.c. critical graphs. We construct 2-e.c. critical graphs of each order \(\geq 9\), and describe a 2-e.c.-preserving operation: replication of an edge.'' The authors also investigate which of the following operations [cf. \textit{F. Harary} and \textit{G. W. Wilcox}, Boolean operations on graphs, Math. Scand. 20, 41-51 (1967; Zbl 0152.22801)] on a pair of graphs \(G\), \(H\) preserve the property of being \(n\)-e.c. for small values of \(n\): disjunction, lexicographic product, symmetric difference, categorical product, all defined on vertex set \(V(G)\times V(H)\), respectively with an edge \((a,b)(c,d)\) iff \(ac\in E(G)\) or \(bd\in E(H)\) or both, iff \(ac\in E(G)\) or both \(a=c\) and \(bd\in E(H)\), iff exactly one of \(ac\in E(G)\) or \(bd\in E(H)\), and iff \(ac\in E(G)\) and \(bd\in E(H)\); and total join, defined, when \(V(G)\cap V(H)=\emptyset\), on vertex set \(V(G)\cup V(H)\), with edge set \(E(G)\cup E(H)\cup \{ac\mid a\in V(G)\), \(c\in V(H)\}\).