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, M.E., Montero, L.P.
Formato:	JOUR
Materias:	Biclique biclique graph clique graph iterated biclique operator
Acceso en línea:	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	todo:paper_15710653_v35_nC_p241_Groshaus
record_format	dspace
spelling	todo:paper_15710653_v35_nC_p241_Groshaus2023-10-03T16:27:03Z The number of convergent graphs under the biclique operator with no twin vertices is finite Groshaus, M.E. Montero, L.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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.E. Montero, L.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.
format	JOUR
author	Groshaus, M.E. Montero, L.P.
author_facet	Groshaus, M.E. Montero, L.P.
author_sort	Groshaus, M.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
url	http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p241_Groshaus
work_keys_str_mv	AT groshausme thenumberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite AT monterolp thenumberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite AT groshausme numberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite AT monterolp numberofconvergentgraphsunderthebicliqueoperatorwithnotwinverticesisfinite
_version_	1782028981366685696

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

Ejemplares similares