A Helly theorem for geodesic convexity in strongly dismantlable graphs

✍ Scribed by Norbert Polat

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 476 KB
• Volume: 140
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0178-7

✦ Synopsis

A (finite or infinite) graph G is strongly dismantlable if its vertices can be linearly ordered x o ..... x~ so that, for each ordinal fl < ~, there exists a strictly increasing finite sequence (i~)0~<j~<n of ordinals such that i o = fl, i, = ct and xi~ +1 is adjacent with x~j and with all neighbors of x~j in the subgraph of G induced by {xy: fl ~<7 ~<~ }. We show that the Helly number for the geodesic convexity of such a graph equals its clique number. This generalizes a result of Bandelt and Mulder (1990) for dismantlable graphs. We also get an analogous equality dealing with infinite families of convex sets.