Uniquely monopolar-partitionable block graphs
Xuegang Chen, Jing Huang
Abstract
As a common generalization of bipartite and split graphs, monopolar
graphs are defined in terms of the existence of certain vertex partitions.
It has been shown that to determine whether a graph has such a partition
is NP-complete for general graphs and polynomial for several classes of graphs.
In this paper, we investigate graphs that admit a unique such partition
and call them uniquely monopolar-partitionable graphs.
By employing a tree trimming technique, we obtain a characterization of
uniquely monopolar-partitionable block graphs.
Our characterization implies a polynomial time algorithm for recognizing them.
Full Text: PDF PostScript