Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T14:18:29.006Z Has data issue: false hasContentIssue false
  • English
  • Français

A Theorem on Reconstruction of Random Graphs

Published online by Cambridge University Press:  12 September 2008

Peter J. Cameron  and
Cleide Martins
Peter J. Cameron
Affiliation:
School of Mathematical Sciences, Queen Mary and Westfield College, Mile End Road, London E1 4NS
Cleide Martins
Affiliation:
School of Mathematical Sciences, Queen Mary and Westfield College, Mile End Road, London E1 4NS
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we prove that given a finite collection of finite graphs, and the subsets of vertices of a random graph G that induce those graphs, it is almost always possible to uniquely reconstruct a class of graphs equivalent to G.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 1 , March 1993 , pp. 1 - 9
Copyright
Copyright © Cambridge University Press 1993

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]Blass, A. and Harary, F. (1979) Properties of Almost all Graphs and Complexes. J. Graph Theory 3 225–240.Google Scholar
[2]Cameron, P. J. (1984) Aspects of the Random Graph. In: Bollobás, B. (ed.) Graph Theory and Combinatorics, Acad. Press 65–79.Google Scholar
[3]Cameron, P. J. (1990) Oligomorphic Permutation Groups. London Math. Soc. Lecture Note Series 152, Cambridge University Press.Google Scholar
[4]Fagin, R. (1976) Probabilities on Finite Models. J. Symbolic Logic 41 (1) 50–58.CrossRefGoogle Scholar
[5]Goodman, A. W. (1959) On Sets of Acquaintances and Strangers at Any Party. Amer. Math. Monthly 66 778–783.Google Scholar
[6]Reed, B. (1987) A Semi-Strong Perfect Graph Theorem. J. Combinatorial Theory B 43 223–240.CrossRefGoogle Scholar
[7]Rado, R. (1964) Universal Graphs and Universal Functions. Acta Arith. 9 331–340.Google Scholar
[8]Seidel, J. J. (1973) A Survey of Two-Graphs. Accademia Nazionale dei Lincei Atti dei Convegni Lincei 17, Colloquio Internazionale Sulle Teorie Combinatorie, Roma.Google Scholar
[9]Thomas, S. (1991) Reducts of the Random Graph. J. Symbolic Logic 56 176–181.Google Scholar