JPRM-Vol. 1 (2009), Issue 1, pp. 101 – 114

Open Access Full-Text PDF
**A. P. Santhakumaran, P. Titus**

**Abstract: **For a connected graph \(G\) of order \(p ≥ 2\), a set \(S ⊆ V (G)\) is an \(x\)-geodominating set of \(G\) if each vertex \(v ∈ V (G)\) lies on an \(x-y\) geodesic for some element y in \(S\). The minimum cardinality of an \(x\)-geodominating set of G is defined as the \(x\)-geodomination number of \(G\), denoted by gx(G). An \(x\)-geodominating set of cardinality \(g_x(G)\) is called a \(g_x\)-set of \(G\). A connected \(x\)-geodominating set of G is an \(x\)-geodominating set S such that the subgraph \(G[S]\) induced by \(S\) is connected. The minimum cardinality of a connected \(x\)-geodominating set of \(G\) is defined as the connected \(x\)-geodomination number of \(G\) and is denoted by \(cg_x(G)\). A connected \(x\)-geodominating set of cardinality \(cg_x(G)\) is called a \(cg_x\)-set of \(G\). We determine bounds for it and find the same for some special classes of graphs. If \(p, a\) and \(b\) are positive integers such that \(2 ≤ a ≤ b ≤ p − 1\), then there exists a connected graph G of order \(p\), \(g_x(G) = a\) and \(cg_x(G) = b\) for some vertex \(x\) in \(G\). Also, if \(p\), \(d\) and \(n\) are integers such that \(2 ≤ d ≤ p − 2\) and \(1 ≤ n ≤ p\), then there exists a connected graph \(G\) of order \(p\), diameter \(d\) and \(cg_x(G) = n\) for some vertex \(x\) in \(G\). For positive integers \(r\), \(d\) and \(n\) with \(r ≤ d ≤ 2r\), there exists a connected graph \(G\) with rad \(G = r\), \(diam G = d\) and \(cg_x(G) = n\) for some vertex \(x\) in \(G\).