Article ID Journal Published Year Pages File Type
417925 Discrete Applied Mathematics 2016 11 Pages PDF
Abstract

A biclique of a graph GG is a maximal induced complete bipartite subgraph of GG. The biclique graph of GG denoted by KB(G)KB(G), is the intersection graph of all the bicliques of GG. The biclique graph can be thought as an operator between the class of all graphs. The iterated biclique graph of GG denoted by KBk(G)KBk(G), is the graph obtained by applying the biclique operator kk successive times to GG. The associated problem is deciding whether an input graph converges, diverges or is periodic under the biclique operator when kk grows to infinity. All possible behaviors were characterized recently and an O(n4)O(n4) algorithm for deciding the behavior of any graph under the biclique operator was also given. In this work we prove new structural results of biclique graphs. In particular, we prove that every false-twin-free graph with at least 13 vertices is divergent. These results lead to a linear time algorithm to solve the same problem.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,