Discrete Mathematics & Theoretical Computer Science, Vol 16, No 2

Font Size:  Small  Medium  Large

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