Products of Geodesic Graphs and the Geodetic Number of Products

• Autorzy: Jake A. Soloff , Rommy A. Márquez , Louis M. Friedler
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

geodesic graph; geodetic number; Cartesian products

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 1
• Strony: 35-42

Daty

wydano

2015-02-01

otrzymano

2012-08-27

poprawiono

2013-09-11

zaakceptowano

2014-01-13

online

2015-02-06

Twórcy

autor

Jake A. Soloff

• Department of Mathematics Brown University Providence, RI 02912 USA

autor

Rommy A. Márquez

• Department of Computer Science and Mathematics Arcadia University Glenside, PA 19038 USA

autor

Louis M. Friedler

• Department of Computer Science and Mathematics Arcadia University Glenside, PA 19038 USA

Bibliografia

• [1] A.P. Santhakumaran and P. Titus, Geodesic graphs, Ars Combin. 99 (2011) 75-82.
• [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]
• [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]
• [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]
• [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]
• [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]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1774