Abstract | ||
---|---|---|
Given a monotone graphical property Q, how large should d(n) be to ensure that if (Hn) is any sequence of graphs satisfying |Hn| = n and δ(Hn) ≥ d(n), then almost every induced subgraph of Hn has property Q? We prove essentially best possible results for the following monotone properties: (i) k-connected for fixed k, (ii) Hamiltonian. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1016/S0012-365X(01)00345-4 | Discrete Mathematics |
Keywords | Field | DocType |
induced subgraph,best possible result,following monotone property,random induced graph,monotone graphical property,property q,fixed k,monotone properties,random induced graphs,satisfiability | Has property,Discrete mathematics,Graph,Combinatorics,Hamiltonian (quantum mechanics),Induced subgraph,Monotone polygon,Mathematics | Journal |
Volume | Issue | ISSN |
248 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
B. Bollobas | 1 | 195 | 79.32 |
P. Erdos | 2 | 1 | 0.35 |
R. J. Faudree | 3 | 174 | 38.15 |
Cecil C. Rousseau | 4 | 85 | 14.21 |
R. H. Schelp | 5 | 609 | 112.27 |