Finding intersection models: From chordal to Helly circular-arc graphs

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2012
Materias:
Matemática
Chordal graphs
Clique-tree
Helly circular-arc graphs
Intersection models
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/84095
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-84095
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
Chordal graphs
Clique-tree
Helly circular-arc graphs
Intersection models
spellingShingle Matemática
Chordal graphs
Clique-tree
Helly circular-arc graphs
Intersection models
Alcón, Liliana Graciela
Gutiérrez, Marisa
Finding intersection models: From chordal to Helly circular-arc graphs
topic_facet Matemática
Chordal graphs
Clique-tree
Helly circular-arc graphs
Intersection models
description 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.
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 Finding intersection models: From chordal to Helly circular-arc graphs
title_short Finding intersection models: From chordal to Helly circular-arc graphs
title_full Finding intersection models: From chordal to Helly circular-arc graphs
title_fullStr Finding intersection models: From chordal to Helly circular-arc graphs
title_full_unstemmed Finding intersection models: From chordal to Helly circular-arc graphs
title_sort finding intersection models: from chordal to helly circular-arc graphs
publishDate 2012
url http://sedici.unlp.edu.ar/handle/10915/84095
work_keys_str_mv AT alconlilianagraciela findingintersectionmodelsfromchordaltohellycirculararcgraphs
AT gutierrezmarisa findingintersectionmodelsfromchordaltohellycirculararcgraphs
bdutipo_str Repositorios
_version_ 1764820488371044353

Ejemplares similares