| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
Uniquely monopolar-partitionable block graphs
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.
Cited literature [17 references]
https://hal.inria.fr/hal-01185613
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 5:13:41 PM
Last modification on : Thursday, September 7, 2017 - 1:03:44 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:12:21 AM
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 5:13:41 PM
Last modification on : Thursday, September 7, 2017 - 1:03:44 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:12:21 AM
File
dmtcs-16-2-2.pdf
Publisher files allowed on an open archive