Name
Abstract | ||
|---|---|---|
A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of $K_4$. As a generalization, we ask for the minimum number of $K_4$-subdivisions that are contained in every $3$-connected graph on $n$ vertices. We prove that there are $\Omega(n^3)$ such $K_4$-subdivisions and show that the order of this bound is tight for infinitely many graphs. We further investigate a better bound in dependence on $m$ and prove that the computational complexity of the problem of counting the exact number of $K_4$-subdivisions is $\#P$-hard. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.disc.2015.06.004 | Discrete Mathematics |
DocType | Volume | Issue |
Journal | 338 | 12 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tillmann Miltzow | 1 | 37 | 16.31 |
| Jens M. Schmidt | 2 | 0 | 1.69 |
| Mingji Xia | 3 | 0 | 0.68 |