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. |
Year | Venue | Keywords |
---|---|---|
2012 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | Bipartite power,Interval bigraph,Bipartite permutation graph,Closure property,NP-completeness |
Field | DocType | Volume |
Graph theory,Discrete mathematics,Complete bipartite graph,Bigraph,Combinatorics,Edge-transitive graph,Bipartite graph,Foster graph,3-dimensional matching,Blossom algorithm,Mathematics | Journal | 14.0 |
Issue | ISSN | Citations |
2.0 | 1462-7264 | 1 |
PageRank | References | Authors |
0.38 | 8 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoshio Okamoto | 1 | 170 | 28.50 |
Yota Otachi | 2 | 161 | 37.16 |
Ryuhei Uehara | 3 | 528 | 75.38 |