Computation of independent fixed geodetic number of graphs

<p>Let <span class="math inline">\(S\)</span> be an independent set of a connected graph <span class="math inline">\(G\)</span> of order atleast <span class="math inline">\(2\)</span>. A set <span class="math inline">\(S' \subseteq V(G)-S\)</span> is an <span class="math inline">\(S\)</span>-fixed geodetic set of <span class="math inline">\(G\)</span> if each vertex <span class="math inline">\(v\)</span> in <span class="math inline">\(G\)</span> lies on an <span class="math inline">\(x-y\)</span> geodesic for some <span class="math inline">\(x\in S\)</span> and <span class="math inline">\(y\in S'\)</span>. The <span class="math inline">\(S\)</span>-fixed geodetic number <span class="math inline">\(g_s(G)\)</span> of <span class="math inline">\(G\)</span> is the minimum cardinality of an <span class="math inline">\(S\)</span>-fixed geodetic set of <span class="math inline">\(G\)</span>. The independent fixed geodetic number of <span class="math inline">\(G\)</span> is <span class="math inline">\(g_{if}(G) = min \left\{g_s(G)\right\}\)</span>, where the minimum is taken over all independent sets <span class="math inline">\(S\)</span> in <span class="math inline">\(G\)</span>. An independent fixed geodetic set of cardinality <span class="math inline">\(g_{if}(G)\)</span> is called a <span class="math inline">\(g_{if}\)</span>-set of <span class="math inline">\(G\)</span>. We determine bounds for it and characterize graphs which realize these bounds. Also, the relations with the vertex geodomination number, vertex independence number and vertex covering number of graphs are studied. Some realization results based on the parameter <span class="math inline">\(g_{if}(G)\)</span> are generated. Finally, two algorithms are designed to compute the independent fixed geodetic number <span class="math inline">\(g_{if}(G)\)</span> and their complexity results are analyzed.</p>