###### Options

# Counting K₄-Subdivisions

Publikationstyp

Journal Article

Publikationsdatum

2014-11-18

Sprache

English

TORE-URI

Enthalten in

Volume

338

Issue

12

Start Page

2387

End Page

2392

Article Number

10183

Citation

Discrete Mathematics (2014)

Publisher DOI

Scopus ID

ArXiv ID

A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of K₄. As a generalization, we ask for the minimum number of K₄-subdivisions that are contained in every 3-connected graph on n vertices. We prove that there are Ω(n³) such K₄-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₄-subdivisions is #P-hard.