Cliques and extended triangles : A necessary condition for planar clique graphs

By generalizing the idea of extended triangle of a graph, we succeed in obtaining a common framework for the result of Roberts and Spencer about clique graphs and the one of Szwarcfiter about Helly graphs. We characterize Helly and 3-Helly planar graphs using extended triangles. We prove that if a p...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2004
Materias:
Matemática
Clique graphs
Extended triangles
Helly graphs
Planar graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/83260
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-83260
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Clique graphs
Extended triangles
Helly graphs
Planar graphs
spellingShingle Matemática
Clique graphs
Extended triangles
Helly graphs
Planar graphs
Alcón, Liliana Graciela
Gutiérrez, Marisa
Cliques and extended triangles : A necessary condition for planar clique graphs
topic_facet Matemática
Clique graphs
Extended triangles
Helly graphs
Planar graphs
description By generalizing the idea of extended triangle of a graph, we succeed in obtaining a common framework for the result of Roberts and Spencer about clique graphs and the one of Szwarcfiter about Helly graphs. We characterize Helly and 3-Helly planar graphs using extended triangles. We prove that if a planar graph G is a clique graph, then every extended triangle of G must be a clique graph. Finally, we show the extended triangles of a planar graph which are clique graphs. Any one of the obtained characterizations are tested in O(n2) time.
format Articulo
Articulo
author Alcón, Liliana Graciela
Gutiérrez, Marisa
author_facet Alcón, Liliana Graciela
Gutiérrez, Marisa
author_sort Alcón, Liliana Graciela
title Cliques and extended triangles : A necessary condition for planar clique graphs
title_short Cliques and extended triangles : A necessary condition for planar clique graphs
title_full Cliques and extended triangles : A necessary condition for planar clique graphs
title_fullStr Cliques and extended triangles : A necessary condition for planar clique graphs
title_full_unstemmed Cliques and extended triangles : A necessary condition for planar clique graphs
title_sort cliques and extended triangles : a necessary condition for planar clique graphs
publishDate 2004
url http://sedici.unlp.edu.ar/handle/10915/83260
work_keys_str_mv AT alconlilianagraciela cliquesandextendedtrianglesanecessaryconditionforplanarcliquegraphs
AT gutierrezmarisa cliquesandextendedtrianglesanecessaryconditionforplanarcliquegraphs
bdutipo_str Repositorios
_version_ 1764820488440250373

Ejemplares similares