The property in the title is well-known. I am trying to find an original reference to its first appearance in print. The 4th edition of Graphs & Digraphs by Chartrand and Lesniak lists this as Theorem 13.6 and says that it's a generalization of a result by Gilbert, but gives no further reference.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
|
|
|
|
|
4
|
The result you asked about follows instantly from Fagin's proof of the zero-one law for finite graphs. He shows that all of Gaifman's extension axioms have asymptotic probability 1, and "diameter $\leq 2$" is essentially one of the extension axioms. Fagin's paper is "Probabilities on finite models" [J. Symbolic Logic 41 (1976) pp.50-58]. I believe the zero-one law was proved earlier by four Russians, but I don't have access to their paper and don't know whether their method immediately implies the "diameter $\leq2$" result. |
||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
5
|
I think you will find it in Moon, J. W.; Moser, L. Almost all (0,1) matrices are primitive. Studia Sci. Math. Hungar. 1 (1966) 153–156. But I don't have time to visit the library to be sure and I don't see it online. It is certainly in Burtin, Ju. D. Asymptotic estimates of the diameter and the independence and domination numbers of a random graph. (Russian) Dokl. Akad. Nauk SSSR 209 (1973), 765–768. I guess the Gilbert mentioned is Gilbert, E. N. Random graphs. Ann. Math. Statist. 30 (1959) 1141–1144. It isn't clear exactly why... |
||||||
|
