# zbMATH — the first resource for mathematics

On an adjacency property of almost all graphs. (English) Zbl 0973.05043
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 [L. Caccetta, P. Erdős and 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 [P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hung. 14, 295-315 (1963; Zbl 0118.18901)] and called, by Cameron, “the” random graph [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. F. Harary and 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)\}$$.

##### MSC:
 05C35 Extremal problems in graph theory 05C80 Random graphs (graph-theoretic aspects) 05C75 Structural characterization of families of graphs
Full Text: