Subir material

Suba sus trabajos a SEDICI, para mejorar notoriamente su visibilidad e impacto

 

Mostrar el registro sencillo del ítem

dc.date.accessioned 2019-10-11T18:28:37Z
dc.date.available 2019-10-11T18:28:37Z
dc.date.issued 2006
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/83201
dc.description.abstract The clique graph of G, K (G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K-1 (G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete. en
dc.format.extent 1799-1802 es
dc.language en es
dc.subject Clique graphs es
dc.subject Clique-critical graphs es
dc.subject NP-complete problems es
dc.title Clique-critical graphs: Maximum size and recognition en
dc.type Articulo es
sedici.identifier.other doi:10.1016/j.dam.2006.03.024 es
sedici.identifier.other eid:2-s2.0-33745810960 es
sedici.identifier.issn 0166-218X es
sedici.creator.person Alcón, Liliana Graciela es
sedici.subject.materias Ciencias Exactas es
sedici.description.fulltext true es
mods.originInfo.place Facultad de Ciencias Exactas es
sedici.subtype Articulo es
sedici.rights.license Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
sedici.rights.uri http://creativecommons.org/licenses/by-nc-sa/4.0/
sedici.description.peerReview peer-review es
sedici.relation.journalTitle Discrete Applied Mathematics es
sedici.relation.journalVolumeAndIssue vol. 154, no. 13 es


Descargar archivos

Thumbnail
Documento completo
Descargar archivo (390.8Kb) - PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)

Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)