Back to Search
Start Over
Local conditions for exponentially many subdivisions
- Source :
- Combinatorics, Probability and Computing. 26(3)
- Publication Year :
- 2016
-
Abstract
- Given a graph $F$, let $s_t(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 $s_t(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, $s_t(F)$ is polynomial in $t$. Further, for a natural strengthening of the local condition above, we also characterise those $F$ for which $s_t(F)$ is exponential in a power of $t$.<br />Comment: 7 pages, to appear in Combinatorics, Probability and Computing
- Subjects :
- Statistics and Probability
Vertex (graph theory)
Discrete mathematics
business.industry
Applied Mathematics
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Graph
Theoretical Computer Science
Exponential function
Combinatorics
Computational Theory and Mathematics
Exponential growth
010201 computation theory & mathematics
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Mathematics - Combinatorics
Combinatorics (math.CO)
business
QA
Mathematics
Subdivision
Subjects
Details
- ISSN :
- 14692163 and 09635483
- Volume :
- 26
- Issue :
- 3
- Database :
- OpenAIRE
- Journal :
- Combinatorics, Probability and Computing
- Accession number :
- edsair.doi.dedup.....214aab02c55fbb7018176fc2ad73b5a7