On bipartite powers of bigraphs

Abstract : The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.11--20
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990585
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:27:33
Dernière modification le : jeudi 7 septembre 2017 - 01:03:39
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:38:09

Fichier

2132-7332-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990585, version 1

Collections

Citation

Yoshio Okamoto, Yota Otachi, Ryuhei Uehara. On bipartite powers of bigraphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.11--20. 〈hal-00990585〉

Partager

Métriques

Consultations de la notice

80

Téléchargements de fichiers

320