𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Random strongly regular graphs?

✍ Scribed by Peter J. Cameron


Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
289 KB
Volume
273
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis


Strongly regular graphs lie on the cusp between highly structured and unstructured. For example, there is a unique strongly regular graph with parameters (36; 10; 4; 2), but there are 32548 non-isomorphic graphs with parameters (36; 15; 6; 6). (The ΓΏrst assertion is a special case of a theorem of Shrikhande, while the second is the result of a computer search by McKay and Spence.) In the light of this, it will be di cult to develop a theory of random strongly regular graphs! For certain values of the parameters, we have at least one prerequisite for a theory of random objects: there should be very many of them (e.g. superexponentially many). Two other features we would like are a method to sample from the uniform distribution (this is known in a couple of special cases) and information about how various graph parameters behave as random variables on the uniform distribution. Very little is known but there are a few recent results and some interesting problems. This paper develops no general theory, but explores a few examples and techniques which can be applied in some cases. Thomason has developed a theory of "pseudo-random graphs" which he calls (p; )-jumbled graphs. Some of these graphs are strongly regular, but they are very special strongly regular graphs. I conclude with some speculation about "random jumbled graphs".


πŸ“œ SIMILAR VOLUMES


Random strongly regular graphs?
✍ Peter J. Cameron πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 203 KB
Some new strongly regular graphs
✍ A. E. Brouwer; A. V. Ivanov; M. H. Klin πŸ“‚ Article πŸ“… 1989 πŸ› Springer-Verlag 🌐 English βš– 318 KB
Distance regular graphs of diameter 3 an
✍ A.E Brouwer πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 124 KB

In [1] N.L. Biggs mentions two parameter sets for distance regular graphs that are antipodal covers of a complete graph, for which existence of a corresponding graph was unknown. Here we settle both cases by proving that one does not exist, while there are exactly two nonisomorphic solutions to the

Strongly balanced graphs and random grap
✍ Andrzej RuciΕ„ski; Andrew Vince πŸ“‚ Article πŸ“… 1986 πŸ› John Wiley and Sons 🌐 English βš– 455 KB

The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with u vertices and e edges if and only if I s u -1 s e s ( 2 " ) . This result is applied to a classic question of Erdos and Renyi: What is the probability that a random graph on n vertices

Generating Random Regular Graphs
✍ J. H. Kim; V. H. Vu* πŸ“‚ Article πŸ“… 2006 πŸ› Springer-Verlag 🌐 English βš– 325 KB
On regular and strongly-regular self-com
✍ S.B. Rao πŸ“‚ Article πŸ“… 1985 πŸ› Elsevier Science 🌐 English βš– 589 KB

In this paper we solve 3 of the 6 problems of A. Kotzig on regular and strongly-regular self-complementary graphs, mentioned in "Graph Theory and Related Topics" edited by J.A.