Characterizing and recognizing probe block graphs

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G=(V,E)G=(V,E) is said to be an (unpartitioned) probe block graph if there exist an independent set N⊆VN⊆V and some set E′⊆(N2) such that the graph G′=(V,E∪E′)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.