On the block number of graphs

Link:
Autor/in:
Erscheinungsjahr:
2019
Medientyp:
Text
Schlagworte:
  • Article
  • Article
Beschreibung:
  • A k-block in a graph G is a maximal set of at least k vertices no two of which can be separated in G by deleting fewer than k vertices. The block number beta(G) of G is the maximum integer k for which G contains a k-block. We prove a structure theorem for graphs without a (k+1)-block, showing that every such graph has a tree-decomposition in which every torso has at most k vertices of degree 2k(2) or greater. This yields a qualitative duality, since every graph that admits such a decomposition has block number at most 2k(2). We also study k-blocks in graphs from classes of graphs G that exclude some fixed graph as a topological minor and prove that every G is an element of G satisfies beta(G) <= c (3)root vertical bar G vertical bar for some constant c = c(G). Moreover, we show that every graph of tree-width at least 2k(2) has a minor containing a k-block. This bound is best possible up to a multiplicative constant.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/389c6383-6429-4b8e-a8fa-e867de55ab7c