Almost every graph is divergent under the biclique operator

作者：Groshaus Marina; Guedes Andre L P; Montero Leandro^*

来源：Discrete Applied Mathematics, 2016, 201: 130-140.

DOI：10.1016/j.dam.2015.07.022

• Bicliques
• Biclique graphs
• False-twin-free graphs
• Iterated graph operators
• Graph dynamics

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph of G denoted by KB(G), is the intersection graph of all the bicliques of G. The biclique graph can be thought as an operator between the class of all graphs. The iterated biclique graph of G denoted by KBk(G), is the graph obtained by applying the biclique operator k successive times to G. The associated problem is deciding whether an input graph converges, diverges or is periodic under the biclique operator when k grows to infinity. All possible behaviors were characterized recently and an O(n(4)) 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.

• 出版日期2016-3-11