Yoshio Okamoto ; Yota Otachi ; Ryuhei Uehara - On bipartite powers of bigraphs

dmtcs:576 - Discrete Mathematics & Theoretical Computer Science, August 5, 2012, Vol. 14 no. 2 - https://doi.org/10.46298/dmtcs.576
On bipartite powers of bigraphsArticle

Authors: Yoshio Okamoto ORCID1; Yota Otachi ORCID2; Ryuhei Uehara ORCID2

  • 1 Department of Communication Engineering and Informatics [Tokyo]
  • 2 School of Information Science [Ishikawa]

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.


Volume: Vol. 14 no. 2
Section: Graph Theory
Published on: August 5, 2012
Accepted on: June 9, 2015
Submitted on: April 11, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 438 times.
This article's PDF has been downloaded 553 times.