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