The geodetic domination number of comb product graphs

Abstract

A subset S of vertices in graph G is called a geodetic set if every vertex in V(G) \ S lies on a shortest path between two vertices in S. A subset S of vertices in G is called a dominating set if every vertex in V(G) \ S is adjacent to a vertex in S. The set S is called a geodetic dominating set if S is both geodetic and dominating sets. The geodetic domination number of G, denoted by γg(G), is the minimum cardinality of geodetic domination sets in G. The comb product of connected graphs G and H at vertex o ∈ V(H), denoted by G ∇o H, is a graph obtained by taking one copy of G and |V(G)| copies of H and identifying the ith copy of H at the vertex o to the ith vertex of G. In this paper, we determine an exact value of γg(G ∇o H) for any connected graphs G and H.

Keywords

• comb product, domination number, geodetic domination number, geodetic number