### On bipartite powers of bigraphs

*Yoshio Okamoto, Yota Otachi, Ryuhei Uehara*

#### 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.Full Text: PDF PostScript