On asteroidal sets in chordal graphs

Abstract

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.