On asteroidal sets in chordal graphs

We analyze the relation between three parameters of a chordal graph GG: the number of non-separating cliques nsc(G)nsc(G), the asteroidal number an(G)an(G) and the leafage l(G)l(G). We show that an(G)an(G) is equal to the maximum value of nsc(H)nsc(H) over all connected induced subgraphs HH of GG. As a corollary, we prove that if GG has no separating simplicial cliques then an(G)=l(G)an(G)=l(G).A graph GG is minimal kk-asteroidal if an(G)=kan(G)=k and an(H)3k>3; for k=3k=3 it is the family described by Lekerkerker and Boland to characterize interval graphs. We prove that, for every minimal kk-asteroidal chordal graph, all the above parameters are equal to kk. In addition, we characterize the split graphs that are minimal kk-asteroidal and obtain all the minimal 44-asteroidal split graphs. Finally, we applied our results on asteroidal sets to describe the clutters with kk edges that are minor-minimal in the sense that every minor has less than kk edges.