Intersection Graphs and the Clique Operator

Let P be a class of finite families of finite sets that satisfy a property P. We call ΩP the class of intersection graphs of families in P and CliqueP the class of graphs whose family of cliques is in P. We prove that a graph G is in ΩP if and only if there is a family of complete sets of G which co...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2001
Materias:
Matemática
Intersection Graph
Interval Graph
Chordal Graph
Finite Family
Dual Family
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/134311
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-134311
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
Intersection Graph
Interval Graph
Chordal Graph
Finite Family
Dual Family
spellingShingle Matemática
Intersection Graph
Interval Graph
Chordal Graph
Finite Family
Dual Family
Gutiérrez, Marisa
Intersection Graphs and the Clique Operator
topic_facet Matemática
Intersection Graph
Interval Graph
Chordal Graph
Finite Family
Dual Family
description Let P be a class of finite families of finite sets that satisfy a property P. We call ΩP the class of intersection graphs of families in P and CliqueP the class of graphs whose family of cliques is in P. We prove that a graph G is in ΩP if and only if there is a family of complete sets of G which covers all edges of G and whose dual family is in P. This result generalizes that of Gavril for circular-arc graphs and conduces those of Fulkerson-Gross, Gavril and Monma-Wei for interval graphs, chordal graphs, UV, DV and RDV graphs. Moreover, it leads to the characterization of Helly-graphs and dually chordal graphs as classes of intersection graphs. We prove that if P is closed under reductions, then CliqueP=Ω(P*∩H) (P*= Class of dual families of families in P). We find sufficient conditions for the Clique Operator, K, to map ΩP into ΩP*. These results generalize several known results for particular classes of intersection graphs. Furthermore, they lead to the Roberts-Spencer characterization for the image of K and the Bandelt-Prisner result on K-fixed classes.
format Articulo
Articulo
author Gutiérrez, Marisa
author_facet Gutiérrez, Marisa
author_sort Gutiérrez, Marisa
title Intersection Graphs and the Clique Operator
title_short Intersection Graphs and the Clique Operator
title_full Intersection Graphs and the Clique Operator
title_fullStr Intersection Graphs and the Clique Operator
title_full_unstemmed Intersection Graphs and the Clique Operator
title_sort intersection graphs and the clique operator
publishDate 2001
url http://sedici.unlp.edu.ar/handle/10915/134311
work_keys_str_mv AT gutierrezmarisa intersectiongraphsandthecliqueoperator
bdutipo_str Repositorios
_version_ 1764820454774669313

Ejemplares similares