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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.21--34
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185613
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 17:13:41
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:12:21

Fichier

dmtcs-16-2-2.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185613, version 1

Collections

Citation

Xuegang Chen, Jing Huang. Uniquely monopolar-partitionable block graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.21--34. 〈hal-01185613〉

Partager

Métriques

Consultations de la notice

90

Téléchargements de fichiers

75