The number of convergent graphs under the biclique operator with no twin vertices is finite

The biclique graph of G, K B (G), is the intersection graph of the bicliques of G. Given a graph G, the iterated biclique graph of G, K B k (G), is the graph defined iteratively as follows: K B k + 1 (G) = K B (K B k (G)). Say that a graph G diverges (resp. converges) under the operator KB whenever...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Groshaus, Marina E., Montero, Leandro P.
Publicado:	2009
Materias:	Biclique biclique graph clique graph iterated biclique operator
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p241_Groshaus http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p241_Groshaus
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_15710653_v35_nC_p241_Groshaus
record_format	dspace
spelling	paper:paper_15710653_v35_nC_p241_Groshaus2023-06-08T16:24:25Z The number of convergent graphs under the biclique operator with no twin vertices is finite Groshaus, Marina E. Montero, Leandro P. Biclique biclique graph clique graph iterated biclique operator The biclique graph of G, K B (G), is the intersection graph of the bicliques of G. Given a graph G, the iterated biclique graph of G, K B k (G), is the graph defined iteratively as follows: K B k + 1 (G) = K B (K B k (G)). Say that a graph G diverges (resp. converges) under the operator KB whenever lim k → ∞ V (K B k (G)) = ∞ (resp. lim k → ∞ K B k (G) = K B m (G) for some m). Each of these behaviours were recently characterized. These characterizations lead to a O (n 4) time algorithm for deciding the divergence or convergence of a graph. In this work we prove that any graph with at least 7 bicliques diverges under the biclique operator. Furthermore, we prove that graphs with no twin vertices that are not divergent have at most 12 vertices, which leads to a linear time algorithm to decide if a graph converges or diverges under the biclique operator. © 2009 Elsevier B.V. All rights reserved. Fil:Groshaus, M.E. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Montero, L.P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p241_Groshaus http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p241_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 biclique graph clique graph iterated biclique operator
spellingShingle	Biclique biclique graph clique graph iterated biclique operator Groshaus, Marina E. Montero, Leandro P. The number of convergent graphs under the biclique operator with no twin vertices is finite
topic_facet	Biclique biclique graph clique graph iterated biclique operator
description	The biclique graph of G, K B (G), is the intersection graph of the bicliques of G. Given a graph G, the iterated biclique graph of G, K B k (G), is the graph defined iteratively as follows: K B k + 1 (G) = K B (K B k (G)). Say that a graph G diverges (resp. converges) under the operator KB whenever lim k → ∞ V (K B k (G)) = ∞ (resp. lim k → ∞ K B k (G) = K B m (G) for some m). Each of these behaviours were recently characterized. These characterizations lead to a O (n 4) time algorithm for deciding the divergence or convergence of a graph. In this work we prove that any graph with at least 7 bicliques diverges under the biclique operator. Furthermore, we prove that graphs with no twin vertices that are not divergent have at most 12 vertices, which leads to a linear time algorithm to decide if a graph converges or diverges under the biclique operator. © 2009 Elsevier B.V. All rights reserved.
author	Groshaus, Marina E. Montero, Leandro P.
author_facet	Groshaus, Marina E. Montero, Leandro P.
author_sort	Groshaus, Marina E.
title	The number of convergent graphs under the biclique operator with no twin vertices is finite
title_short	The number of convergent graphs under the biclique operator with no twin vertices is finite
title_full	The number of convergent graphs under the biclique operator with no twin vertices is finite
title_fullStr	The number of convergent graphs under the biclique operator with no twin vertices is finite
title_full_unstemmed	The number of convergent graphs under the biclique operator with no twin vertices is finite
title_sort	number of convergent graphs under the biclique operator with no twin vertices is finite
publishDate	2009
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p241_Groshaus http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p241_Groshaus
work_keys_str_mv	AT groshausmarinae thenumberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite AT monteroleandrop thenumberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite AT groshausmarinae numberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite AT monteroleandrop numberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite
_version_	1768541769568354304

The number of convergent graphs under the biclique operator with no twin vertices is finite

Ejemplares similares