Abstract
We propose a problem concerning the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random graphs. We prove some bounds and demonstrate them in the cases of a d-cube and a two dimensional lattice.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 91-94 |
| Number of pages | 4 |
| Journal | Graphs and Combinatorics |
| Volume | 8 |
| Issue number | 1 |
| DOIs | |
| State | Published - Mar 1992 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics