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)\}\).

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