Uniquely monopolar-partitionable block graphs

作者：Chen, Xuegang^*; Huang, Jing

来源：Discrete Mathematics and Theoretical Computer Science, 2014, 16(2): 21-34.

• Monopolar graph
• monopolar partition
• uniquely monopolar-partitionable grap
• block graph
• characterization
• polynomial time algorithm

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 an NP-complete problem for general graphs, and is polynomial time solvable 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 determining whether a block graph is uniquely monopolar-partitionable.

• 出版日期2014
• 单位北京工业大学; 华北电力大学; 华北电力大学（保定）