ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Random graphs and covering graphs of posets (1986)

Bollobás, Béla ; Brightwell, Graham ; Nešetřil, Jaroslav

Springer

Order 3 (1986), S. 245-255

add to mindlist on the mindlist

Details

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

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit