Counting K_4-Subdivisions

Tillmann Miltzow; Jens M. Schmidt; Mingji Xia

doi:10.1016/j.disc.2015.06.004

paper

Counting K_4-Subdivisions

arXiv:1411.4819 · doi:10.1016/j.disc.2015.06.004

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 $Ω (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.

5 figures