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