Characterizing and recognizing probe block graphs.

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G = ( V , E ) is said to be an (unpartitioned) probe block graph if there exist an independent set N ⊆ V and some set E ′ ⊆ ( N 2 ) such that the graph G ′ = ( V , E ∪ E ′ ) is a block graph; if such an independent set N is given, G is called a partitioned probe block graph. In this note we give good characterizations for probe block graphs, in both unpartitioned and partitioned cases. As a result, partitioned and unpartitioned probe block graphs can be recognized in linear time. [ABSTRACT FROM AUTHOR]