1. Convexity in Helly Graphs: Selection and Almost Fixed Point Properties for Multifunctions
- Author
-
Michael B. Smyth and Rueiher Tsaur
- Subjects
Discrete mathematics ,Graph convexity ,General Computer Science ,Neighbourhood (graph theory) ,Selection property ,Computer Science::Computational Geometry ,Fixed point ,Fixed-point property ,Graph ,Convexity ,Theoretical Computer Science ,Almost fixed point property ,Combinatorics ,Multifunctions ,Helly's theorem ,Fixed clique property ,Mathematics::Metric Geometry ,Helly graphs ,Computer Science(all) ,Mathematics - Abstract
In this paper, a notion of convexity structure for graphs, called neighbourhood convexity, is introduced. It is shown that neighbourhood convexity is exactly the graph convexity for Helly graphs to be 2-Helly. We then consider various neighbourhood-convexity almost fixed point properties for Helly graphs. In particular, we show that for any positive number p, every Helly graph has the neighbourhood convexity ⌈ p 2 ⌉ -almost fixed point property for p-weak multifunctions; and any self-mapping neighbourhood convexity strong multifunction has a selection. more...
- Published
- 2006
- Full Text
- View/download PDF