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 independent sets , 1≤i≤k, such that the graph G′ obtained from G by adding some new edges between certain vertices inside the sets , 1≤i≤k, is a block graph; if the independent sets are given, G is called a partitioned k-probe block graph. In this paper we give good characterizations for 2-probe block graphs, in both unpartitioned and partitioned cases. As an algorithmic implication, partitioned and unpartitioned 2-probe block graphs can be recognized in linear time, improving a recognition algorithm of cubic time complexity previously obtained by Chang et al. (2011) in .
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com