Abstract | ||
---|---|---|
A study of the orders of maximal induced trees in a random graph G p with small edge probability p is given. In particular, it is shown that the giant component of almost every G p , where p = c/n and c > 1 is a constant, contains only very small maximal trees (that are of a specific type) and very large maximal trees. The presented results provide an elementary proof of a conjecture from [3] that was confirmed recently in [4] and [5]. |
Year | DOI | Venue |
---|---|---|
1988 | 10.1016/0012-365X(88)90215-4 | Discrete Mathematics |
Keywords | Field | DocType |
maximal induced tree,sparse random graph,random graph | Random regular graph,Discrete mathematics,Combinatorics,Random graph,Elementary proof,Giant component,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
72 | 1-3 | Annals of Discrete Mathematics |
Citations | PageRank | References |
5 | 2.69 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomasz Łuczak | 1 | 225 | 40.26 |
Zbigniew Palka | 2 | 43 | 14.55 |