Options
Counting K₄-Subdivisions
Publikationstyp
Journal Article
Date Issued
2014-11-18
Sprache
English
Author(s)
TORE-URI
Journal
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.
Subjects
3-connected graphs
Counting K -subdivisions 4
Cycles
Computer Science - Discrete Mathematics
Computer Science - Discrete Mathematics
Mathematics - Combinatorics