A cut locus for finite graphs and the farthest point mapping. (English) Zbl 1322.05048

Summary: We reflect upon an analogue of the cut locus, a notion classically studied in differential geometry, for finite graphs. The cut locus \(C(x)\) of a vertex \(x\) shall be the graph induced by the set of all vertices \(y\) with the property that no shortest path between \(x\) and \(z\), \(z \neq y\), contains \(y\). The cut locus coincides with the graph induced by the vertices realizing the local maxima of the distance function. The function \(F\) mapping a vertex \(x\) to \(F(x)\), the set of global maxima of the distance function from \(x\), is the farthest point mapping. Among other things, we observe that if, for a vertex \(x\), \(C(x)\) is connected, then \(C(x)\) is the graph induced by \(F(x)\), and prove that the farthest point mapping has period 2. Elaborating on the analogy with Geometry, we study graphs satisfying Steinhaus’ condition, i.e. graphs for which the farthest point mapping is single-valued and involutive.


05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)


Full Text: DOI


[2] Baues, O.; Peyerimhoff, N., Geodesics in non-positively curved plane tessellations, Adv. Geom., 6, 243-263 (2006) · Zbl 1098.53034
[3] Baues, O.; Peyerimhoff, N., Curvature and geometry of tessellating plane graphs, Discrete Comput. Geom., 25, 141-159 (2001) · Zbl 0963.05031
[4] Berger, M., A Panoramic View of Riemannian Geometry (2002), Springer
[6] Buckley, F., Self-Centered Graphs, Annals New York Acad. Sci., 576, 71-78 (1989) · Zbl 0792.05050
[7] Buckley, F., The eccentric digraph of a graph, Congr. Numer., 149, 65-76 (2001) · Zbl 0989.05034
[8] Buckley, F., Self-centered graphs with a given radius, Congr. Numer., 23, 211-215 (1979) · Zbl 0426.05034
[9] Buckley, F.; Harary, F., Distance in Graphs (1990), Addison-Wesley · Zbl 0688.05017
[10] Buckley, F.; Harary, F.; Quintas, L. V., Extremal results on the geodetic number of a graph, Sci. Sin. A, 2, 17-26 (1988) · Zbl 0744.05021
[11] Chartrand, G.; Erwin, D.; Johns, G. L.; Zhang, P., Boundary vertices in graphs, Discrete Math., 263, 25-34 (2003) · Zbl 1020.05024
[12] Chartrand, G.; Escuadro, H.; Zhang, P., Detour Distance in Graphs, J. Combin. Math. Combin. Comput., 53, 75-94 (2005) · Zbl 1074.05029
[13] Chartrand, G.; Harary, F.; Zhang, P., On the geodetic number of a graph, Networks, 39, 1-6 (2002) · Zbl 0987.05047
[14] Chartrand, G.; Zhang, P., Distance in graphs — taking the long view, AKCE J. Graphs. Combin., 1, 1-13 (2004) · Zbl 1062.05051
[15] Chung, F. R.K., Diameters of graphs: Old problems and new results, Congress. Numer., 60, 295-317 (1987) · Zbl 0695.05029
[16] Croft, H. T.; Falconer, K. J.; Guy, R. K., Unsolved Problems in Geometry (1991), Springer · Zbl 0748.52001
[17] Erdős, P.; Pach, J.; Pollack, R.; Tuza, Zs., Radius, diameter, and minimum degree, J. Combin. Theory, Ser. B, 47, 73-79 (1989) · Zbl 0686.05029
[18] Gimbert, J.; Miller, M.; Ruskey, F.; Ryan, J., Iterations of eccentric digraphs, Bull. Inst. Combin. Appl., 45, 41-50 (2005) · Zbl 1079.05032
[19] Goddard, W.; Oellermann, O. R., Distance in graphs, (Dehmer, Matthias, Structural Analysis of Complex Networks (2009), Birkhäuser)
[21] Harary, F.; Loukakis, E.; Tsouros, C., The geodetic number of a graph, Math. Comput. Modelling, 17, 89-95 (1993) · Zbl 0825.68490
[22] Higuchi, Y., Combinatorial curvature for planar graphs, J. Graph Theory, 38, 220-229 (2001) · Zbl 0996.05041
[23] Itoh, J.; Vîlcu, C., Cut locus structures on graphs, Discrete Math., 312, 524-531 (2012) · Zbl 1233.05166
[27] Kay, D. C.; Chartrand, G., A characterization of certain ptolemaic graphs, Canad. J. Math., 17, 342-346 (1965) · Zbl 0139.17301
[29] Kiyohara, K., On Blaschke manifolds and harmonic manifolds, Sémin. Théor. Spectr. Géom., 6, 33-37 (1987-1988) · Zbl 1149.53312
[30] Klassert, S.; Lenz, D.; Peyerimhoff, N.; Stollmann, P., Elliptic operators on planar graphs: unique continuation for eigenfunctions and nonpositive curvature, Proc. Amer. Math. Soc., 134, 1549-1559 (2005) · Zbl 1094.05016
[31] Kobayashi, S., On conjugate and cut loci, (Global Differential Geometry (1989), MAA: MAA Washington D.C), 140-169 · Zbl 0683.53043
[32] Myers, S. B., Connections between differential geometry and topology. I. Simply connected surfaces, Duke Math. J., 1, 376-391 (1935) · JFM 61.0787.02
[33] Myers, S. B., Connections between differential geometry and topology. II: Closed surfaces, Duke Math. J., 2, 95-102 (1936) · JFM 62.0861.02
[35] Parthasarathy, K. R.; Nandakumar, R., Unique eccentric point graphs, Discrete Math., 46, 69-74 (1983) · Zbl 0513.05032
[36] Poincaré, H., Sur les lignes géodésiques des surfaces convexes, Trans. Amer. Math. Soc., 6, 237-274 (1905) · JFM 36.0669.01
[37] Vîlcu, C., On two conjectures of Steinhaus, Geom. Dedicata, 79, 267-275 (2000) · Zbl 0971.52003
[38] Villani, C., Regularity of optimal transport and cut locus: From nonsmooth analysis to geometry to smooth analysis, Discrete Contin. Dyn. Syst., 30, 559-571 (2011) · Zbl 1225.49048
[39] von Mangoldt, A., Über diejenigen Punkte auf positiv gekrümmten Flächen, welche die Eigenschaft haben, daß die von ihnen ausgehenden geodätischen Linien nie aufhören, kürzeste Linien zu sein, J. Reine Angew. Math., 91, 23-54 (1881) · JFM 13.0578.01
[40] Whitehead, J. H.C., On the covering of a complete space by the geodesics through a point, Ann. of Math., 36, 2, 679-704 (1935) · Zbl 0012.27802
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.