On an adjacency property of almost all graphs (Q5937580): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:43, 5 March 2024
scientific article; zbMATH DE number 1619831
Language | Label | Description | Also known as |
---|---|---|---|
English | On an adjacency property of almost all graphs |
scientific article; zbMATH DE number 1619831 |
Statements
On an adjacency property of almost all graphs (English)
0 references
28 November 2001
0 references
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)\}\).
0 references
adjacency property
0 references
\(n\)-existentially closed
0 references
random graph
0 references
critical graphs
0 references
Boolean operations
0 references