Xuegang Chen ; Jing Huang - Uniquely monopolar-partitionable block graphs

dmtcs:2073 - Discrete Mathematics & Theoretical Computer Science, May 6, 2014, Vol. 16 no. 2 - https://doi.org/10.46298/dmtcs.2073
Uniquely monopolar-partitionable block graphsArticle

Authors: Xuegang Chen 1,2; Jing Huang 3

  • 1 Department of Mathematics (Beijing)
  • 2 Department of Applied Mathematics
  • 3 Department of Mathematics and Statistics

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.


Volume: Vol. 16 no. 2
Section: PRIMA 2013
Published on: May 6, 2014
Submitted on: December 27, 2013
Keywords: Monopolar graph,monopolar partition,uniquely monopolar-partitionable grap,block graph,characterization,polynomial time algorithm,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Consultation statistics

This page has been seen 426 times.
This article's PDF has been downloaded 533 times.