Block-cutvertex trees and block-cutvertex partitions
type: Item
instance of: scholarly article
title: Block-cutvertex trees and block-cutvertex partitions
zbMATH Open document ID: 1010.05020
DOI: 10.1016/S0012-365X(01)00461-7
author: Curtiss Barefoot
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: The graph whose vertices are the blocks and cutvertices of a connected graph \(G\), and whose edges join the cutvertices with those blocks to which they belong is called the block-cutvertex graph of \(G\). Some other authors showed that a graph \(H\) is the block-cutvertex graph of a graph if and only if \(H\) is a tree in which the distance between any two leaves is even. The concept of a block-cutvertex partition of a tree \(T\) is introduced in this article (it is a collection \(\{T_1,\dots, T_k\}\) of block-cutvertex trees such that each \(T_i\) is a subtree of \(T\) and each edge of \(T\) is in exactly one \(T_i\)). The author proves that a tree has such a partition if and only if it does not have a perfect matching. He presents various concepts and algorithms related to block-cutvertex partitions.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1838909
zbMATH Keywords: block-cutvertex graph
zbMATH Keywords: block-cutvertex partitions
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00461-7
OpenAlex ID: W2024684573
Recommended article: Vertex partitioning problems on partial k-trees
Recommended article: On tree-partitions of graphs
Recommended article: Characterizing Block Graphs in Terms of their Vertex-Induced Partitions
Recommended article: Tree partitioning via vertex deletion
Recommended article: On tree partitions
Recommended article: Partitioning graphs of bounded tree-width
Recommended article: Vertex partitioning problems on graphs with bounded tree width
Recommended article: Blocks and Cut Vertices of the Buneman Graph
Recommended article: Partition complexes and trees
description: scientific article; zbMATH DE number 1838909