Given a connected graph and a vertex x ∈ V (G), the geodesic graph Px(G) has the same vertex set as G with edges uv iff either v is on an x − u geodesic path or u is on an x − v geodesic path. A characterization is given of those graphs all of whose geodesic graphs are complete bipartite. It is also shown that the geodetic number of the Cartesian product of Km,n with itself, where m, n ≥ 4, is equal to the minimum of m, n and eight.
@article{bwmeta1.element.doi-10_7151_dmgt_1774,
author = {Jake A. Soloff and Rommy A. M\'arquez and Louis M. Friedler},
title = {Products of Geodesic Graphs and the Geodetic Number of Products},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {35-42},
zbl = {1307.05063},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1774}
}
Jake A. Soloff; Rommy A. Márquez; Louis M. Friedler. Products of Geodesic Graphs and the Geodetic Number of Products. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 35-42. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1774/
[1] A.P. Santhakumaran and P. Titus, Geodesic graphs, Ars Combin. 99 (2011) 75-82. | Zbl 1265.05204
[2] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000).
[3] B. Brešar, M. Kovše and A. Tepeh Horvat, Geodetic sets in graphs in: M. Dehmer (Eds.), Structural Analysis of Complex Networks, Springer Science+Business Media, LLC, New York (2011) 197-218. doi:10.1007/978-0-8176-4789-6 8[Crossref] | Zbl 1221.05107
[4] B. Brešar, S. Klavžar and A. Tepeh Horvat, On the geodetic number and related metric sets in Cartesian product graphs, Discrete Math. 308 (2008) 5555-5561. doi:10.1016/j.disc.2007.10.007[WoS][Crossref] | Zbl 1200.05060
[5] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modelling 17 (1993) 89-95. doi:10.1016/0895-7177(93)90259-2[Crossref][WoS] | Zbl 0825.68490
[6] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1-6. doi:10.1002/net.10007[Crossref] | Zbl 0987.05047
[7] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo and M.L. Puertas, On the geodetic and the hull numbers in strong product graphs, Comput. Math. Appl. 60 (2010) 3020-3031. doi:10.1016/j.camwa.2010.10.001[WoS][Crossref] | Zbl 1207.05043
[8] T. Jiang, I. Pelayo and D. Pritikin, Geodesic convexity and Cartesian products in graphs, manuscript (2004).
[9] Y. Ye, C. Lu and Q. Liu, The geodetic numbers of Cartesian products of graphs, Math. Appl. 20 (2007) 158-163. | Zbl 1125.05058