Geochromatic number of Cartesian product of some graphs

Abstract

In a graph G, a set S ⊆ V(G) is called a geodetic set if every vertex of G lies on a shortest u-v path for some u, v ∈ S, the minimum cardinality among all geodetic sets is called the geodetic number and is denoted by g_n(G). A set C ⊆ V(G) is called a chromatic set if C contains all vertices of different colors in G, the minimum cardinality among all chromatic sets is called the chromatic number and is denoted by χ(G). A geochromatic set Sc ⊆ V(G) is both a geodetic set and a chromatic set. The geochromatic number χ_gc(G) of G is the minimum cardinality among all geochromatic sets of G. In this paper we determine the geochromatic number of cartesian product of standard graphs and derive general results, that prove some of the existing results on products as particular cases. Also some of the existing results are shown to be incorrect.