Artículo
Finding intersection models: From chordal to Helly circular-arc graphs
Fecha de publicación:
03/2012
Editorial:
Elsevier Science
Revista:
Discrete Mathematics
ISSN:
0012-365X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
Every chordal graph G admits a representation as the intersection graph of a family of subtrees of a tree. A classic way of finding such an intersection model is to look for a maximum spanning tree of the valuated clique graph of G. Similar techniques have been applied to find intersection models of chordal graph subclasses as interval graphs and path graphs. In this work, we extend those methods to be applied beyond chordal graphs: we prove that a graph G can be represented as the intersection of a Helly separating family of graphs belonging to a given class if and only if there exists a spanning subgraph of the clique graph of G satisfying a particular condition. Moreover, such a spanning subgraph is characterized by its weight in the valuated clique graph of G. The specific case of Helly circular-arc graphs is treated. We show that the canonical intersection models of those graphs correspond to the maximum spanning cycles of the valuated clique graph.
Palabras clave:
CHORDAL GRAPHS
,
CLIQUE-TREE
,
HELLY CIRCULAR-ARC GRAPHS
,
INTERSECTION MODELS
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
Alcón, Liliana Graciela; Gutierrez, Marisa; Finding intersection models: From chordal to Helly circular-arc graphs; Elsevier Science; Discrete Mathematics; 312; 6; 3-2012; 1148-1157
Compartir
Altmétricas