Almost every graph is divergent under the biclique operator

DOI10.1016/J.DAM.2015.07.022MaRDI QIDQ908300zbMATH OpenOpenAlexFDO

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

Publication date 4 February 2016

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

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)

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.

Recommendations

• On the iterated biclique operator
• The number of convergent graphs under the biclique operator with no twin vertices is finite
• On the edge‐biclique graph and the iterated edge‐biclique operator
• On the termination of some biclique operators on multipartite graphs
• scientific article; zbMATH DE number 1842907

Cites work

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

Cited in

(14)

• Biclique graphs of interval bigraphs
• On the iterated biclique operator
• Biclique graph of bipartite permutation graphs
• On the iterated edge-biclique operator
• The number of convergent graphs under the biclique operator with no twin vertices is finite
• scientific article; zbMATH DE number 1842907 (Why is no real title available?)
• Diclique digraphs
• On bicliques and the second clique graph of suspensions
• Clique‐convergence is undecidable for automatic graphs
• On cliques and bicliques
• On the edge‐biclique graph and the iterated edge‐biclique operator
• Intersection graph of maximal stars
• Biclique graphs of split graphs
• Vertex removal in biclique graphs

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)