On bipartite powers of bigraphs

Access this Article

Abstract

The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper、 we investigate abipartite analogue of graph powers、 which we call bipartite powers of bigraphs. We show that the classes of bipartitepermutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem ofrecognizing bipartite powers is NP-complete in general.

Journal

  • Discrete Mathematics and Theoretical Computer Science

    Discrete Mathematics and Theoretical Computer Science 14(2), 11-20, 2012

    Discrete Mathematics and Theoretical Computer Science

Codes

  • NII Article ID (NAID)
    120005147908
  • Text Lang
    ENG
  • Article Type
    journal article
  • ISSN
    1365-8050
  • Data Source
    IR 
Page Top