𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Properties of almost all graphs and complexes

✍ Scribed by Andreas Blass; Frank Harary

Book ID
102892054
Publisher
John Wiley and Sons
Year
1979
Tongue
English
Weight
809 KB
Volume
3
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries.

To this end, we propose the first-order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph (u,, . . . , u,, vl,. . . , v,), there exists another vertex w adjacent to each ui and not adjacent to any vi. A simple counting argument proves that for each n, almost all graphs satisfy Axiom n. It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H, almost all graphs have an induced subgraph isomorphic to H. (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all graphs are connected with diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicia1 complexes.

πŸ“œ SIMILAR VOLUMES

Almost all Cayley graphs are hamiltonian
Almost all Cayley graphs are hamiltonian
✍ Meng Jixiang; Huang Qiongxiang πŸ“‚ Article πŸ“… 1996 πŸ› Institute of Mathematics, Chinese Academy of Scien 🌐 English βš– 278 KB
Almost all steinhaus graphs have diamete
Almost all steinhaus graphs have diameter 2
✍ Neal Brand πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 300 KB πŸ‘ 1 views

## Abstract A Steinhaus graph is a graph with __n__ vertices whose adjacency matrix (__a__~i, j~) satisfies the condition that __a__~i, j~ ο£½ __a__~a‐‐1, j‐‐1~ + __a__ ~i‐‐1, j~ (mod 2) for each 1 < __i__ < __j__ ≀ __n__. It is clear that a Steinhaus graph is determined by its first row. In [3] Brin

Set intersection representations for alm
Set intersection representations for almost all graphs
✍ Eaton, Nancy; Grable, David A. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 581 KB

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if &(G) is defined to be the minimum number of labels with which G may be repre