Almost every graph is divergent under the biclique operator

DOI10.1016/J.DAM.2015.07.022zbMATH Open1329.05280arXiv1408.6063OpenAlexW1582366387MaRDI QIDQ908300FDOQ908300

Marina Groshaus, Leandro Montero, André L. P. Guedes

Publication date: 4 February 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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 graphs. The iterated biclique graph of $G$ denoted by $K{B}^k(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.

Full work available at URL: https://arxiv.org/abs/1408.6063

zbMATH Keywords

graph dynamicsbicliquesbiclique graphsfalse-twin-free graphsiterated graph operators

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Locally \(C_6\) graphs are clique divergent
• Incidence matrices and interval graphs
• Über iterierte Clique-Graphen
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Clique graphs and Helly graphs
• Biclique graphs and biclique matrices
• A partial characterization of clique graphs
• A characterization of clique graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• The clique operator on cographs and serial graphs
• Clique Graph Recognition Is NP-Complete
• Sur deux propriétés des classes d'ensembles
• Point determination in graphs
• Bicliques in graphs. I: Bounds on their number
• Algorithm Theory - SWAT 2004
• Generating bicliques of a graph in lexicographic order
• On the generation of bicliques of a graph
• Equivariant collapses and the homotopy type of iterated clique graphs
• The number of convergent graphs under the biclique operator with no twin vertices is finite
• On the Iterated Biclique Operator
• Clique divergent graphs with unbounded sequence of diameters
• A family of clique divergent graphs with linear growth
• Dismantlings and iterated clique graphs
• Whitney triangulations, local girth and iterated clique graphs
• Bicliques and eigenvalues
• The icosahedron is clique divergent
• The clique operator on graphs with few \(P_{4}\)'s

Cited In (11)

• Biclique graph of bipartite permutation graphs
• On the iterated edge-biclique operator
• Title not available (Why is that?)
• Diclique digraphs
• Clique‐convergence is undecidable for automatic graphs
• On bicliques and the second clique graph of suspensions
• On the edge‐biclique graph and the iterated edge‐biclique operator
• On cliques and bicliques
• Intersection graph of maximal stars
• Biclique graphs of split graphs
• Biclique graphs of interval bigraphs

This page was built for publication: Almost every graph is divergent under the biclique operator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908300)