Block-cutvertex trees and block-cutvertex partitions

DOI10.1016/S0012-365X(01)00461-7MaRDI QIDQ1849911zbMATH OpenOpenAlexFDO

Authors Curtiss Barefoot

Publication date 2 December 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(01)00461-7

zbMATH Keywords

block-cutvertex graphblock-cutvertex partitions

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• Vertex partitioning problems on partial k-trees
• On tree-partitions of graphs
• Characterizing block graphs in terms of their vertex-induced partitions
• Tree partitioning via vertex deletion
• On tree partitions
• Partitioning graphs of bounded tree-width
• Vertex partitioning problems on graphs with bounded tree width
• Blocks and cut vertices of the Buneman graph
• Partition complexes and trees

Cited in

(11)

• Distance labeling scheme and split decomposition
• On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees
• Multi-distance granularity structural \(\alpha \)-subtree index of generalized Bethe trees
• Enumeration of BC-subtrees of trees
• On algorithms for enumerating BC-subtrees of unicyclic and edge-disjoint bicyclic graphs
• Patterns in Khovanov link and chromatic graph homology
• scientific article; zbMATH DE number 5040143 (Why is no real title available?)
• On spiro and polyphenyl hexagonal chains with respect to the number of BC-subtrees
• A bound on the dissociation number
• Algorithms for enumerating multiple leaf-distance granular regular \(\alpha\)-subtree of unicyclic and edge-disjoint bicyclic graphs
• On block-related derived graphs

This page was built for publication: Block-cutvertex trees and block-cutvertex partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849911)