Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-19T23:51:02.512Z Has data issue: false hasContentIssue false
  • English
  • Français

Properties of Classes of Random Graphs

Published online by Cambridge University Press:  12 September 2008

Neal Brand  and
Steve Jackson
Neal Brand
Affiliation:
Department of Mathematics, University of North Texas, Denton, TX 76203, USA
Steve Jackson
Affiliation:
Department of Mathematics, University of North Texas, Denton, TX 76203, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

In [11] it is shown that the theory of almost all graphs is first-order complete. Furthermore, in [3] a collection of first-order axioms are given from which any first-order property or its negation can be deduced. Here we show that almost all Steinhaus graphs satisfy the axioms of almost all graphs and conclude that a first-order property is true for almost all graphs if and only if it is true for almost all Steinhaus graphs. We also show that certain classes of subgraphs of vertex transitive graphs are first-order complete. Finally, we give a new class of higher-order axioms from which it follows that large subgraphs of specified type exist in almost all graphs.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 4 , December 1994 , pp. 435 - 454
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bailey, C. K. and Dymacek, W. M. (1988) Regular Steinhaus graphs. Congressus Numerantium 66 45–47.Google Scholar
[2]Billingsley, P. (1979) Probability and Measure, John Wiley and Sons.Google Scholar
[3]Blass, A. and Harary, F. (1976) Properties of almost all graphs and complexes. J. Graph Theory 3 225–240.CrossRefGoogle Scholar
[4]Bollobás, B. (1985) Random Graphs, Academic Press.Google Scholar
[5]Brand, N. (1992) Almost all Steinhaus graphs have diameter two. Journal of Graph Theory 16 213–219.CrossRefGoogle Scholar
[6]Brand, N., Curran, S., Das, S. and Jacob, T. (1993) Probability of diameter two for Steinhaus graphs. Discrete Applied Math 41 165–171.CrossRefGoogle Scholar
[7]Brigham, R. C., Deo, N. and Dutton, R. D. (preprint) Some properties of Steinhaus graphs.Google Scholar
[8]Brigham, R. C. and Dutton, R. D. (1990) Distances and diameters in Steinhaus graphs. Congressus Numerantium 76 7–14.Google Scholar
[9]Dymacek, W. M. (1986) Bipartite Steinhaus graphs. Discrete Math. 59 9–20.CrossRefGoogle Scholar
[10]Dymacek, W. M. (1990) Small cycles in Steinhaus graphs. Congressus Numerantium 70 41–52.Google Scholar
[11]Fagin, R. (1976) Probabilities on finite models. J. Symbolic Logic 41 50–58.CrossRefGoogle Scholar
[12]Harborth, H. (1972) Solution to Steinhaus' problem with plus and minus signs. J. Combinatorial Theory 12 (A) 253–259.CrossRefGoogle Scholar
[13]Knuth, D. (1973) The Art of Computer Programming. Volume 1: Fundamentals of Algorithms, Addison-Wesley.Google Scholar
[14]Steinhaus, H. (1963) One Hundred Problems in Elementary Mathematics, Elinsford, New York.Google Scholar