Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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 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.

Registro:

Documento: Artículo
Título:On the iterated biclique operator
Autor:Groshaus, M.; Montero, L.P.
Filiación:Departamento de Computaciõn, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave: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ño:2013
Volumen:73
Número:2
Página de inicio:181
Página de fin:190
DOI: http://dx.doi.org/10.1002/jgt.21666
Título revista:Journal of Graph Theory
Título revista abreviado:J. Graph Theory
ISSN:03649024
CODEN:JGTHD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v73_n2_p181_Groshaus

Referencias:

  • Alcõn, L., Faria, L., De Figueiredo, C.M.H., Gutierrez, M., Clique graph recognition is NP-complete (2006) Graph Theor Concepts Comput Sci, 4271, pp. 269-277
  • Bandelt, H.-J., Prisner, E., Clique graphs and Helly graphs (1991) J Combin Theory ser, 51 (1), pp. 34-45
  • Booth, K., Lueker, G., Testing for the consecutive ones property interval graphs, and graph planarity using PQ-tree algorithms (1976) J Comput Syst. Sci, 13 (3), pp. 335-379
  • Brandstädt, A., Le, V., Spinrad, J.P., (1999) Graph Classes: A Survey, , SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
  • De Mello, C.P., Morgana, A., Liverani, M., The clique operator on graphs with few P4's (2006) Discrete Appl Math, 154 (3), pp. 485-492
  • Dias, V.M.F., De Figueiredo, C.M.H., Szwarcfiter, J.L., Generating bicliques of a graph in lexicographic order (2005) Theor Comput Sci, 337 (13), pp. 240-248
  • Dias, V.M.F., De Figueiredo, C.M.H., Szwarcfiter, J.L., On the generation of bicliques of a graph (2007) Discrete Appl Math, 155 (14), pp. 1826-1832
  • Escalante, F., Über iterierte Clique-Graphen (1973) Abh Math Sem Univ Hamburg, 39, pp. 59-68
  • Pizaña, L.F.M.A., Villarroel-Flores, R., Equivariant collapses and the homotopy type of iterated clique graphs (2008) Discrete Math, 308, pp. 3199-3207
  • Frías-Armenta, M.E., Neumann-Lara, V., Pizaña, M.A., Dismantlings and iterated clique graphs (2004) Discrete Math, 282 (13), pp. 263-265
  • Fulkerson, D.R., Gross, O.A., Incidence matrices and interval graphs (1965) Pacific J Math, 15, pp. 835-855
  • Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs (1974) J Combin Theory ser, 16, pp. 47-56
  • Groshaus, M., Szwarcfiter, J.L., Biclique graphs and biclique matrices (2010) J Graph Theory, 63 (1), pp. 1-16
  • Groshaus, M.E., (2006) Bicliques, Cliques, Neighborhoods y la Propiedad de Helly, , Ph.D. Thesis, Universidad de Buenos Aires
  • Hamelink, R.C., A partial characterization of clique graphs (1968) J Combin Theory, 5, pp. 192-197
  • Hedetniemi, S.T., Slater, P.J., Line graphs of triangleless graphs and iterated clique graphs (1972) Graph Theory and Applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; Dedicated to the Memory of J. W. T. Youngs), Lecture Notes in Mathematics, Springer, Berlin, 303, pp. 139-147
  • 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 (13), pp. 183-191
  • Larriõn, F., Neumann-Lara, V., A family of clique divergent graphs with linear growth (1997) Graphs Combin, 13 (3), pp. 263-266
  • Larriõn, F., Neumann-Lara, V., Clique divergent graphs with unbounded sequence of diameters (1999) Discrete Math, 197-198, pp. 491-501. , 16th British Combinatorial Conference (London, 1997)
  • Larriõn, F., Neumann-Lara, V., Locally C6 graphs are clique divergent (2000) Discrete Math, 215 (13), pp. 159-170
  • Larriõn, F., Neumann-Lara, V., Pizaña, M.A., Whitney triangulations local girth and iterated clique graphs (2002) Discrete Math, 258 (13), pp. 123-135
  • Lehot, P.G.H., An optimal algorithm to detect a line graph and output its root graph (1974) J ACM, 21 (4), pp. 569-575
  • McKee, T.A., McMorris, F.R., (1999) Topics in Intersection Graph Theory, , SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
  • Lara, V.N., Clique divergence in graphs (1981) Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), pp. 563-569. , volume 25 of Colloq. Math. Soc. János Bolyai, North-Holland, Amsterdam
  • Pizaña, M.A., The icosahedron is clique divergent (2003) Discrete Math, 262 (13), pp. 229-239
  • Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) J Combin Theory ser B, 10, pp. 102-108
  • Szpilrajn-Marczewski, E., Sur deux propriétés des classes d'ensembles (1945) Fund Math, 33, pp. 303-307

Citas:

---------- APA ----------
Groshaus, M. & Montero, L.P. (2013) . On the iterated biclique operator. Journal of Graph Theory, 73(2), 181-190.
http://dx.doi.org/10.1002/jgt.21666
---------- CHICAGO ----------
Groshaus, M., Montero, L.P. "On the iterated biclique operator" . Journal of Graph Theory 73, no. 2 (2013) : 181-190.
http://dx.doi.org/10.1002/jgt.21666
---------- MLA ----------
Groshaus, M., Montero, L.P. "On the iterated biclique operator" . Journal of Graph Theory, vol. 73, no. 2, 2013, pp. 181-190.
http://dx.doi.org/10.1002/jgt.21666
---------- VANCOUVER ----------
Groshaus, M., Montero, L.P. On the iterated biclique operator. J. Graph Theory. 2013;73(2):181-190.
http://dx.doi.org/10.1002/jgt.21666