The connected vertex geodomination number of a graph

Abstract

For a connected graph GG of order p≥2p≥2, a set S⊆V(G)S⊆V(G) is an xx-geodominating set of GG if each vertex v∈V(G)v∈V(G) lies on an x−yx−y geodesic for some element y in SS. The minimum cardinality of an xx-geodominating set of G is defined as the xx-geodomination number of GG, denoted by gx(G). An xx-geodominating set of cardinality gx(G)gx(G) is called a gxgx-set of GG. A connected xx-geodominating set of G is an xx-geodominating set S such that the subgraph G[S]G[S] induced by SS is connected. The minimum cardinality of a connected xx-geodominating set of GG is defined as the connected xx-geodomination number of GG and is denoted by cgx(G)cgx(G). A connected xx-geodominating set of cardinality cgx(G)cgx(G) is called a cgxcgx-set of GG. We determine bounds for it and find the same for some special classes of graphs. If p,ap,a and bb are positive integers such that 2≤a≤b≤p−12≤a≤b≤p−1, then there exists a connected graph G of order pp, gx(G)=agx(G)=a and cgx(G)=bcgx(G)=b for some vertex xx in GG. Also, if pp, dd and nn are integers such that 2≤d≤p−22≤d≤p−2 and 1≤n≤p1≤n≤p, then there exists a connected graph GG of order pp, diameter dd and cgx(G)=ncgx(G)=n for some vertex xx in GG. For positive integers rr, dd and nn with r≤d≤2rr≤d≤2r, there exists a connected graph GG with rad G=rG=r, diamG=ddiamG=d and cgx(G)=ncgx(G)=n for some vertex xx in GG.