×
Maddaloni, Alessandro; Zamfirescu, Carol T.

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

Discrete Math. 339, No. 1, 354-364 (2016).
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.

Cited in 1 Document

MathOverflow Questions:

”Antipodal” maps on regular graphs?
Cut Locus in a Graph

MSC:

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

Keywords:

graph distance function; cut locus; farthest point mapping; diameter; injectivity radius

Software:

MathOverflow
PDF BibTeX XML Cite
\textit{A. Maddaloni} and \textit{C. T. Zamfirescu}, Discrete Math. 339, No. 1, 354--364 (2016; Zbl 1322.05048)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] R. Bacher, (mathoverflow.net/users/4556), “Antipodal” maps on regular graphs? http://mathoverflow.net/questions/64804 (version: 2011-05-15).
[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
[5] J. Boland, M. Miller, The eccentric digraph of a digraph. In: Proc. 12th Australasian Workshop Combin. Algorithms (AWOCA 2001) 66-70.
[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)
[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)
[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)
[20] F. Harary, Graph Theory. Addison-Wesley Series in Mathematics, 1969.
[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
[24] J. Itoh, C. Vîlcu, Every graph is a cut locus. arXiv:1103.1759v3 [math.DG].
[25] J. Itoh, C. Vîlcu, On the number of cut locus structures on graphs. arXiv:1103.1764v1 [math.CO].
[26] J. Itoh, C. Vîlcu, Orientable cut locus structures on graphs. arXiv:1103.3136v1 [math.DG].
[27] Kay, D. C.; Chartrand, G., A characterization of certain ptolemaic graphs, Canad. J. Math., 17, 342-346, (1965) · Zbl 0139.17301
[28] M. Keller, N. Peyerimhoff, F. Pogorzelski, Sectional curvature of polygonal complexes with planar substructures. arXiv:1407.4024 [math.MG]. · Zbl 1377.53055
[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 Washington D.C), 140-169
[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
[34] J. O’Rourke, (mathoverflow.net/users/6094). Cut Locus in a Graph. http://mathoverflow.net/questions/58212 (version: 2011-03-12).
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.