Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:The number of convergent graphs under the biclique operator with no twin vertices is finite
Autor:Groshaus, M.E.; Montero, L.P.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Biclique; biclique graph; clique graph; iterated biclique operator
Año:2009
Volumen:35
Número:C
Página de inicio:241
Página de fin:246
DOI: http://dx.doi.org/10.1016/j.endm.2009.11.040
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p241_Groshaus

Referencias:

  • Alcón, L., Faria, L., de Figueiredo, C.M.H., Gutierrez, M., Clique graph recognition is NP-complete (2006) Lecture Notes in Comput. Sci., 4271, pp. 269-277. , Graph-theoretic concepts in computer science
  • Frías-Armenta, M.E., Neumann-Lara, V., Pizaña, M.A., Dismantlings and iterated clique graphs (2004) Discrete Math., 282, pp. 263-265
  • Groshaus, M.E., Montero, L.P., On the iterated biclique operator Proceedings of the VI ALIO/EURO Workshop on Applied Combinatorial Optimization, p. 2008. , pp. CD-ROM Version
  • Groshaus, M.E., Szwarcfiter, J.L., (2008) Biclique graphs, , manuscript
  • Hamelink, R.C., A partial characterization of clique graphs (1968) J. Combinatorial Theory, 5, pp. 192-197
  • Larrión, F., de Mello, C.P., Morgana, A., Neumann-Lara, V., Pizaña, M.A., The clique operator on cographs and serial graphs (2004) Discrete Math., 282, pp. 183-191
  • Larrión, F., Neumann-Lara, V., Pizaña, M.A., Whitney triangulations, local girth and iterated clique graphs (2002) Discrete Math., 258, pp. 123-135
  • Larrión, F., Pizaña, M.A., Villarroel-Flores, R., Equivariant collapses and the homotopy type of iterated clique graphs (2008) Discrete Math., 308, pp. 3199-3207
  • Montero, L.P., Convergencia y divergencia del grafo biclique iterado, (2008), Master's thesis, Departamento de Computación. Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires; Neumann Lara, V., Clique divergence in graphs (1978) Algebraic methods in graph theory, 1-2. , Szeged
  • Neumann Lara, V., Clique divergence in graphs (1981) Colloq. Math. Soc. János Bolyai, 25, pp. 563-569. , North-Holland, Amsterdam
  • Pizaña, M.A., The icosahedron is clique divergent (2003) Discrete Math., 262, pp. 229-239
  • Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) J. Combinatorial Theory Ser. B, 10, pp. 102-108

Citas:

---------- APA ----------
Groshaus, M.E. & Montero, L.P. (2009) . The number of convergent graphs under the biclique operator with no twin vertices is finite. Electronic Notes in Discrete Mathematics, 35(C), 241-246.
http://dx.doi.org/10.1016/j.endm.2009.11.040
---------- CHICAGO ----------
Groshaus, M.E., Montero, L.P. "The number of convergent graphs under the biclique operator with no twin vertices is finite" . Electronic Notes in Discrete Mathematics 35, no. C (2009) : 241-246.
http://dx.doi.org/10.1016/j.endm.2009.11.040
---------- MLA ----------
Groshaus, M.E., Montero, L.P. "The number of convergent graphs under the biclique operator with no twin vertices is finite" . Electronic Notes in Discrete Mathematics, vol. 35, no. C, 2009, pp. 241-246.
http://dx.doi.org/10.1016/j.endm.2009.11.040
---------- VANCOUVER ----------
Groshaus, M.E., Montero, L.P. The number of convergent graphs under the biclique operator with no twin vertices is finite. Electron. Notes Discrete Math. 2009;35(C):241-246.
http://dx.doi.org/10.1016/j.endm.2009.11.040