1Department of Communication Engineering and Informatics [Tokyo] (Department of Communication Engineering and Informatics, Graduate School of Informatics and Engineering, University of Electro-Communications, Chofugaoka 1-5-1, Chofu, Tokyo, 182-8585 Japan - Japon)
2School of Information Science [Ishikawa] (School of Information Science, Japan Advanced Institute of Science and Technology, Asahidai 1-1, Nomi, Ishikawa 923-1292, Japan - Japon)
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.
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
