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

dmtcs:576 - Discrete Mathematics & Theoretical Computer Science, August 5, 2012, Vol. 14 no. 2
On bipartite powers of bigraphs

Authors: Okamoto, Yoshio and Otachi, Yota and Uehara, Ryuhei

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.


Source : oai:HAL:hal-00990585v1
Volume: Vol. 14 no. 2
Section: Graph Theory
Published on: August 5, 2012
Submitted on: April 11, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 58 times.
This article's PDF has been downloaded 61 times.