On the iterated biclique operator
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 the bicliques of G. We say that a graph G diverges (or converges or is periodic) under an operator F whenever limk→∞|V(Fk(G))|=∞ (limk→∞Fk(G)=Fm(G) f...
Guardado en:
Autores principales: | , |
---|---|
Formato: | JOUR |
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03649024_v73_n2_p181_Groshaus |
Aporte de: |
id |
todo:paper_03649024_v73_n2_p181_Groshaus |
---|---|
record_format |
dspace |
spelling |
todo:paper_03649024_v73_n2_p181_Groshaus2023-10-03T15:27:41Z On the iterated biclique operator Groshaus, M. Montero, L.P. biclique graphs bicliques clique graphs divergent graphs graph dynamics iterated graph operators Biclique Bicliques Clique graphs divergent graphs Graph dynamics Polynomial approximation Graph theory 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 the bicliques of G. We say that a graph G diverges (or converges or is periodic) under an operator F whenever limk→∞|V(Fk(G))|=∞ (limk→∞Fk(G)=Fm(G) for some m, or Fk(G)=Fk+s(G) for some k and s≥2, respectively). Given a graph G, the iterated biclique graph of G, denoted by KBk(G), is the graph obtained by applying the biclique operator k successive times to G. In this article, we study the iterated biclique graph of G. In particular, we classify the different behaviors of KBk(G) when the number of iterations k grows to infinity. That is, we prove that a graph either diverges or converges under the biclique operator. We give a forbidden structure characterization of convergent graphs, which yield a polynomial time algorithm to decide if a given graph diverges or converges. This is in sharp contrast with the situsation for the better known clique operator, where it is not even known if the corresponding problem is decidable. © 2012 Wiley Periodicals, Inc. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03649024_v73_n2_p181_Groshaus |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
topic |
biclique graphs bicliques clique graphs divergent graphs graph dynamics iterated graph operators Biclique Bicliques Clique graphs divergent graphs Graph dynamics Polynomial approximation Graph theory |
spellingShingle |
biclique graphs bicliques clique graphs divergent graphs graph dynamics iterated graph operators Biclique Bicliques Clique graphs divergent graphs Graph dynamics Polynomial approximation Graph theory Groshaus, M. Montero, L.P. On the iterated biclique operator |
topic_facet |
biclique graphs bicliques clique graphs divergent graphs graph dynamics iterated graph operators Biclique Bicliques Clique graphs divergent graphs Graph dynamics Polynomial approximation Graph theory |
description |
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 the bicliques of G. We say that a graph G diverges (or converges or is periodic) under an operator F whenever limk→∞|V(Fk(G))|=∞ (limk→∞Fk(G)=Fm(G) for some m, or Fk(G)=Fk+s(G) for some k and s≥2, respectively). Given a graph G, the iterated biclique graph of G, denoted by KBk(G), is the graph obtained by applying the biclique operator k successive times to G. In this article, we study the iterated biclique graph of G. In particular, we classify the different behaviors of KBk(G) when the number of iterations k grows to infinity. That is, we prove that a graph either diverges or converges under the biclique operator. We give a forbidden structure characterization of convergent graphs, which yield a polynomial time algorithm to decide if a given graph diverges or converges. This is in sharp contrast with the situsation for the better known clique operator, where it is not even known if the corresponding problem is decidable. © 2012 Wiley Periodicals, Inc. |
format |
JOUR |
author |
Groshaus, M. Montero, L.P. |
author_facet |
Groshaus, M. Montero, L.P. |
author_sort |
Groshaus, M. |
title |
On the iterated biclique operator |
title_short |
On the iterated biclique operator |
title_full |
On the iterated biclique operator |
title_fullStr |
On the iterated biclique operator |
title_full_unstemmed |
On the iterated biclique operator |
title_sort |
on the iterated biclique operator |
url |
http://hdl.handle.net/20.500.12110/paper_03649024_v73_n2_p181_Groshaus |
work_keys_str_mv |
AT groshausm ontheiteratedbicliqueoperator AT monterolp ontheiteratedbicliqueoperator |
_version_ |
1782029019696332800 |