Biclique graphs of interval bigraphs
| Autor: | Edmilson Pereira da Cruz, Juan Pablo Puppo, André Luiz Pires Guedes, Marina Groshaus |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Applied Mathematics
Bipartite permutation graphs 0211 other engineering and technologies Bigraph 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Intersection graph 01 natural sciences Complete bipartite graph Graph Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Recognition algorithm Time complexity Mathematics |
| Zdroj: | Discrete Applied Mathematics. 281:134-143 |
| ISSN: | 0166-218X |
| Popis: | The biclique graph K B ( G ) is the intersection graph of all the bicliques of a graph G . The aim of our work is to recognize graphs that are biclique graphs of interval bigraphs ( IBG ). In this paper we prove that K B ( IBG ) ⊂ K 1 , 4 -free co-comparability graphs. We also study the class of biclique graphs of proper interval bigraphs ( PIB ). Recall that PIB is equal to the class of bipartite permutation graphs ( BPG ). We present a characterization of the class K B ( PIB ) and of the biclique graphs of a subclass of PIB that leads to a polynomial time recognition algorithm. We also present characterizations of biclique graphs of some classes such as complete graphs, trees and graphs with girth at least 5. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect