Name
Abstract | ||
|---|---|---|
Given a graph F, let (st)( F) be the number of subdivisions of F, each with a different vertex set, which one can guarantee in a graph G in which every edge lies in at least t copies of F. In 1990, Tuza asked for which graphs F and large t, one has that (st)(F) is exponential in a power of t. We show that, somewhat surprisingly, the only such F are complete graphs, and for every F which is not complete, (st)(F) is polynomial in t. Further, for a natural strengthening of the local condition above, we also characterize those F for which (st)(F) is exponential in a power of t. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1017/S0963548316000365 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Exponential function,Vertex (geometry),Polynomial,Subdivision,Mathematics,Exponential growth | Journal | 26 |
Issue | ISSN | Citations |
3 | 0963-5483 | 0 |
PageRank | References | Authors |
0.34 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hong Liu | 1 | 39 | 8.54 |
| Maryam Sharifzadeh | 2 | 11 | 3.83 |
| Katherine Staden | 3 | 6 | 3.31 |