ISSN:
1572-9273
Keywords:
06A10
;
60C05
;
Poset
;
diagram
;
covering graph
;
random graph
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n -1+η(n) ,where η(n) is bounded away from 0, then there is a constant k 0〉0 such that, for a.e. G p , c(G p )≥k 0 n 1+η(n) .In other words, to make G p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n -1+η(n) , where η(n)→0, thenc(G p )=o(n 1+η(n) ), almost surely.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00400288
Permalink