Absolute retracts of bipartite graphs |
| |
Institution: | Fachbereich 6, Carl-von-Ossietzky-Universität, D-2900 Oldenburg, Fed. Rep. Germany |
| |
Abstract: | A bipartite graph G is an absolute retract if every isometric embedding g of G into a bipartite graph H is a coretraction (that is, there exists an edge-preserving map h from H to G such that hg is the identity map on G). Examples of absolute retracts are provided by chordal bipartite graphs and the covering graphs of modular lattices of breadth two. We give a construction and several characterizations of bipartite absolute retracts involving Helly type conditions. Bipartite absolute retracts apply to competitive location theory: they are precisely those bipartite graphs on which locational equilibria (Condorcet solutions) always exist.All graphs in this paper are finite, connected, and without loops or multiple edges. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|