Bounds for the geodetic number of the cartesian product of graphs

Abstract

Let G be a connected graph and u and υ be two vertices of G. The set I _G[u, υ] denotes the closed interval consisting of u, υ and all vertices lying on some u-υ geodesic of G.A. subset S of V(G) is called a geodetic cover of G if I _G[S] = V(G), where I _G[S] = U _u,υ∈SI _G[u, υ]. A geodetic cover of G with minimum cardinality is called a geodetic basis. The geodetic number g(G) of G is the order of a geodetic basis of G. In this paper, we give a lower bound and an upper bound for the geodetic number of the cartesian product of any two connected graphs. This result generalizes a result on G × K ₂ obtained by Chartrand, Harary and Zhang in [5].