Bridged graphs
Bridged graphs are graphs in which all isometrically embedded cycles have length 3.
They can be characterized (see [3], [5]) as precisely those graphs, which flag completion are systolic complexes.
The theory of bridged complexes was developed independently of the theory of systolic complexes.
In [1] V. Soltan and V. Chepoi characterize graphs in which the neighboorhoods of convex
sets are convex as graphs in which all isometrically embedded cycles have length 3.
This result was rediscovered later in 1987 by R. Jamison and M. Farber,
which called such graphs bridged.
The basic information on bridged graphs are presented in a survey [4].
Some other papers on the subject, interested from a systolic point of view, are
[2] presenting a very short (algorithmic) proof of a result by R.
Anstee and M. Farber that bridged graphs are dismantlable (a graph
version of collapsibility) and [5] which improves the hyperbolicity bound of 7-systolic complexes.
References
- V. Soltan, V. Chepoi,
Conditions for invariance of set diameter under d-convexification in a graph,
Cybernetics 6 (1983), 14-18.
- V. Chepoi,
Bridged graphs are cop-win graphs: an algorithmic proof,
J. Combin. Th., Ser B 69 (1997), 97-100.
- V. Chepoi,
Graphs of some CAT(0) complexes,
Adv. Appl. Math. 24 (2000), 125-179.
- H.-J. Bandelt, V. Chepoi,
Metric graph theory and geometry: a survey, In J.E. Goodman, J. Pach, and
R. Pollack, eds; Surveys on Discrete and Computational Geometry: twenty years later, vol. 453
of Contemporary Mathematics, pp. 49-86. AMS-IMS-SIAM Joint Summer Research Conference Discrete and Computational Geometry -
Twenty Years Later, 2008.
- V. Chepoi, F. Dragan, B. Estellon, M. Habib, Y. Vaxes,
Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs,
24th Annual ACM Symposium on Computational Geometry, College Park, Maryland, 2008.