Intersection Graphs and the Clique Operator |
| |
Authors: | Marisa Gutierrez |
| |
Affiliation: | (1) Departamento de Matemática, Facultad de Ciencias Exactas, Universidad Nacional de La Plata, C.C. 172, (1900) La Plata, Argentina. e-mail: marisa@cacho.mate.unlp.edu.ar, AR |
| |
Abstract: | 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. Received: August 18, 1997 Final version received: March 30, 1999 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|