Clique-critical graphs: Maximum size and recognition

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<SUB>-1</SUB...

Descripción completa

Detalles Bibliográficos
Autor principal: Alcón, Liliana Graciela
Formato: Articulo
Lenguaje:Inglés
Publicado: 2006
Materias:
Ciencias Exactas
Clique graphs
Clique-critical graphs
NP-complete problems
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/83201
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-83201
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Clique graphs
Clique-critical graphs
NP-complete problems
spellingShingle Ciencias Exactas
Clique graphs
Clique-critical graphs
NP-complete problems
Alcón, Liliana Graciela
Clique-critical graphs: Maximum size and recognition
topic_facet Ciencias Exactas
Clique graphs
Clique-critical graphs
NP-complete problems
description 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<SUB>-1</SUB> (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.
format Articulo
Articulo
author Alcón, Liliana Graciela
author_facet Alcón, Liliana Graciela
author_sort Alcón, Liliana Graciela
title Clique-critical graphs: Maximum size and recognition
title_short Clique-critical graphs: Maximum size and recognition
title_full Clique-critical graphs: Maximum size and recognition
title_fullStr Clique-critical graphs: Maximum size and recognition
title_full_unstemmed Clique-critical graphs: Maximum size and recognition
title_sort clique-critical graphs: maximum size and recognition
publishDate 2006
url http://sedici.unlp.edu.ar/handle/10915/83201
work_keys_str_mv AT alconlilianagraciela cliquecriticalgraphsmaximumsizeandrecognition
bdutipo_str Repositorios
_version_ 1764820488381530116

Ejemplares similares