On asteroidal sets in chordal graphs

We analyze the relation between three parameters of a chordal graph G: the number of non-separating cliques nsc(G), the asteroidal number an(G) and the leafage l(G). We show that an(G) is equal to the maximum value of nsc(H) over all connected induced subgraphs H of G. As a corollary, we prove that...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Alcón, Liliana Graciela
Formato: Articulo
Lenguaje:Inglés
Publicado: 2014
Materias:
Matemática
Asteroidal number
Chordal graphs
Clique separators
Clutters
Leafage
Sperner families
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/85141
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-85141
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
Asteroidal number
Chordal graphs
Clique separators
Clutters
Leafage
Sperner families
spellingShingle Matemática
Asteroidal number
Chordal graphs
Clique separators
Clutters
Leafage
Sperner families
Alcón, Liliana Graciela
On asteroidal sets in chordal graphs
topic_facet Matemática
Asteroidal number
Chordal graphs
Clique separators
Clutters
Leafage
Sperner families
description We analyze the relation between three parameters of a chordal graph G: the number of non-separating cliques nsc(G), the asteroidal number an(G) and the leafage l(G). We show that an(G) is equal to the maximum value of nsc(H) over all connected induced subgraphs H of G. As a corollary, we prove that if G has no separating simplicial cliques then an(G)=l(G). A graph G is minimal k-asteroidal if an(G)=k and an(H)<k for every proper connected induced subgraph H of G. The family of minimal k-asteroidal chordal graphs is unknown for every k>3; for k=3 it is the family described by Lekerkerker and Boland to characterize interval graphs. We prove that, for every minimal k-asteroidal chordal graph, all the above parameters are equal to k. In addition, we characterize the split graphs that are minimal k-asteroidal and obtain all the minimal 4-asteroidal split graphs. Finally, we applied our results on asteroidal sets to describe the clutters with k edges that are minor-minimal in the sense that every minor has less than k edges.
format Articulo
Articulo
author Alcón, Liliana Graciela
author_facet Alcón, Liliana Graciela
author_sort Alcón, Liliana Graciela
title On asteroidal sets in chordal graphs
title_short On asteroidal sets in chordal graphs
title_full On asteroidal sets in chordal graphs
title_fullStr On asteroidal sets in chordal graphs
title_full_unstemmed On asteroidal sets in chordal graphs
title_sort on asteroidal sets in chordal graphs
publishDate 2014
url http://sedici.unlp.edu.ar/handle/10915/85141
work_keys_str_mv AT alconlilianagraciela onasteroidalsetsinchordalgraphs
bdutipo_str Repositorios
_version_ 1764820489004384258

Ejemplares similares