Good characterizations and linear time recognition for 2-probe block graphs

Van Bang Le, Sheng-Lung Peng

Block graphs are graphs in which every block (biconnected component) is a clique. A graph $G=(V,E)$ is said to be an (unpartitioned) $k$-probe block graph if there exist $k$ indepe…