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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2009
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 05178caa a22005417a 4500 | ||
|---|---|---|---|
| 001 | PAPER-8272 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203805.0 | ||
| 008 | 190411s2009 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-71049159216 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Groshaus, M.E. | |
| 245 | 1 | 4 | |a The number of convergent graphs under the biclique operator with no twin vertices is finite |
| 260 | |c 2009 | ||
| 270 | 1 | 0 | |m Groshaus, M.E.; Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina; email: groshaus@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a Frías-Armenta, M.E., Neumann-Lara, V., Pizaña, M.A., Dismantlings and iterated clique graphs (2004) Discrete Math., 282, pp. 263-265 | ||
| 504 | |a 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 | ||
| 504 | |a Groshaus, M.E., Szwarcfiter, J.L., (2008) Biclique graphs, , manuscript | ||
| 504 | |a Hamelink, R.C., A partial characterization of clique graphs (1968) J. Combinatorial Theory, 5, pp. 192-197 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Neumann Lara, V., Clique divergence in graphs (1981) Colloq. Math. Soc. János Bolyai, 25, pp. 563-569. , North-Holland, Amsterdam | ||
| 504 | |a Pizaña, M.A., The icosahedron is clique divergent (2003) Discrete Math., 262, pp. 229-239 | ||
| 504 | |a Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) J. Combinatorial Theory Ser. B, 10, pp. 102-108 | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: PICT 1562 | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, X456, X143 | ||
| 536 | |a Detalles de la financiación: Consejo Nacional de Investigaciones Científicas y Técnicas | ||
| 536 | |a Detalles de la financiación: 1 Partially supported by UBACyT X456, X143 and ANPCyT PICT 1562 Grants and by CONICET, Argentina. 2 Partially supported by UBACyT X456, ANPCyT PICT 1562 and CONICET Grants, Argentina. | ||
| 593 | |a Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a BICLIQUE |
| 690 | 1 | 0 | |a BICLIQUE GRAPH |
| 690 | 1 | 0 | |a CLIQUE GRAPH |
| 690 | 1 | 0 | |a ITERATED BICLIQUE OPERATOR |
| 700 | 1 | |a Montero, L.P. | |
| 773 | 0 | |d 2009 |g v. 35 |h pp. 241-246 |k n. C |p Electron. Notes Discrete Math. |x 15710653 |t Electronic Notes in Discrete Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-71049159216&doi=10.1016%2fj.endm.2009.11.040&partnerID=40&md5=e2cfc330293fa4b4fa589375a3963ae4 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.endm.2009.11.040 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p241_Groshaus |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p241_Groshaus |y Registro en la Biblioteca Digital |
| 961 | |a paper_15710653_v35_nC_p241_Groshaus |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 69225 | ||