×

The geodetic numbers of Cartesian products of graphs. (English) Zbl 1125.05058

Summary: For any two vertices \(u\) and \(v\) in a graph \(G\), a \(u\)-\(v\) geodesic is the shortest path between \(u\) and \(v\). Let \(I(u, v)\) denote the set of all vertices lying on a \(u\)-\(v\) geodesic. For a vertex subset \(S\), let \(I(S)\) denote the union of all \(I(u, v)\) for \(u, v\in S\). The geodetic number \(g(G)\) of a graph \(G\) is the minimum cardinality of a set \(S\) with \(I(S)=V(G)\). In this paper, a sufficient and necessary condition for the equality of \(g(G)\) and \(g(G\times K_3)\) is presented, and for a tree \(T\), we give the geodetic number of \(T\times K_m\) and \(C_n\times K_m\).

MSC:

05C38 Paths and cycles
05C12 Distance in graphs
PDFBibTeX XMLCite