Let \(S\) be an independent set of a connected graph \(G\) of order atleast \(2\). A set \(S' \subseteq V(G)-S\) is an \(S\)-fixed geodetic set of \(G\) if each vertex \(v\) in \(G\) lies on an \(x-y\) geodesic for some \(x\in S\) and \(y\in S'\). The \(S\)-fixed geodetic number \(g_s(G)\) of \(G\) is the minimum cardinality of an \(S\)-fixed geodetic set of \(G\). The independent fixed geodetic number of \(G\) is \(g_{if}(G) = min \left\{g_s(G)\right\}\), where the minimum is taken over all independent sets \(S\) in \(G\). An independent fixed geodetic set of cardinality \(g_{if}(G)\) is called a \(g_{if}\)-set of \(G\). 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 \(g_{if}(G)\) are generated. Finally, two algorithms are designed to compute the independent fixed geodetic number \(g_{if}(G)\) and their complexity results are analyzed.
By a graph \(G = (V,E)\) we mean a finite undirected connected graph without loops and multiple edges. The order and size of \(G\) are denoted by \(p\) and \(q\), respectively. For basic graph theoretic terminology we refer to [1, 3]. For vertices \(x\) and \(y\) in a connected graph \(G\), the distance \(d(x,y)\) is the length of a shortest \(x-y\) path in \(G\). An \(x-y\) path of length \(d(x,y)\) is called an \(x-y\) geodesic. The neighbourhood of a vertex \(v\) is the set \(N(v)\) consisting of all vertices \(u\) which are adjacent with \(v\). A vertex \(v\) is a simplicial vertex if the subgraph induced by its neighbours is complete. The closed interval \(I[x, y]\) consists of all vertices lying on some \(x-y\) geodesic of \(G\). For any two subsets \(A\) and \(B\) in \(V(G)\), \(I[A, B] = \bigcup_{x\in A, y\in B}I[x, y]\).
The concept of vertex geodomination number was introduced in [5] and further studied in [7]. For any vertex \(x\) in \(G\), a set \(S \subseteq V(G)\) is called an \(x\)-geodominating set if every vertex \(v\) in \(G\) lies on an \(x-y\) geodesic for some \(y\) in \(S\). The minimum cardinality of an \(x\)-geodetic set (or \(x\)-geodominating set) of \(G\) is defined as the \(x\)-geodomination number of \(G\), denoted by \(g_x(G)\). An \(x\)-geodominating set of cardinality \(g_x(G)\) is called a \(g_x\)-set. It is proved in [5] that for any vertex \(x\) in \(G\), the \(g_x\)-set is unique and \(1 \leq g_x(G) \leq {p-1}\). Also, the concept of edge fixed geodomination number was introduced and studied in []. Clearly, for any vertex \(x\) in \(G\), \(S = \{x\}\) is an independent set of \(G\) and so an \(x\)-geodominating set of \(G\) is nothing but an \(S\)-fixed geodetic set of \(G\). Now, instead of fixing a single vertex \(x\), we can fix an independent set \(S\). This motivates us to introduce the new parameter independent fixed geodetic number of a graph. Also, a new concept based on independent fixed geodomination number and connectedness is introduced and studied in [8]. The following theorems will be used in the sequel.
Theorem 1.1. [3] Let \(v\) be a vertex of a connected graph \(G\). The following statements are equivalent:
(i) \(v\) is a cut-vertex of \(G\).
(ii) There exist vertices \(u\) and \(w\) distinct from \(v\) such that \(v\) is on every \(u-w\) path.
(iii) There exists a partition of the set of vertices \(V-\left\{v\right\}\) into subsets \(U\) and \(W\) such that for any vertices \(u\in U\) and \(w\in W\), the vertex \(v\) is on every \(u-w\) path.
Theorem 1.2. [2] For every graph \(G\) of order \(p\) containing no isolated vertices, \({\alpha(G) + \beta(G) = p}\).
Theorem 1.3. [5] For any vertex \(x\) in \(G\), \(1\leq g_x(G)\leq {p-1}\).
Theorem 1.4. [5] For any vertex \(x\) in \(G\), every simplicial vertex of \(G\) other than the vertex \(x\) (whether \(x\) is simplicial or not) belongs to the \(g_x\)-set of \(G\).
Throughout this paper \(G\) denotes a connected graph of order atleast 2.
Definition 2.1. Let \(S\) be an independent set of a connected graph \(G\) of order atleast 2. A set \(S' \subseteq V(G)-S\) is an \(S\)-fixed geodetic set of \(G\) if each vertex \(v\) in \(G\) lies on an \(x-y\) geodesic for some \(x\in S\) and \(y\in S'\). The \(S\)-fixed geodetic number \(g_s(G)\) of \(G\) is the minimum cardinality of an \(S\)-fixed geodetic set of \(G\). The independent fixed geodetic number of \(G\) is \(g_{if}(G) = min \left\{g_s(G)\right\}\), where the minimum is taken over all independent sets \(S\) in \(G\). An independent fixed geodetic set of cardinality \(g_{if}(G)\) is called a \(g_{if}\)-set of \(G\).
Example 2.2. For the graph \(G\) given in Figure 1, the independent sets \(S\), their corresponding minimum \(S\)-fixed geodetic sets and the \(S\)-fixed geodetic numbers \(g_s(G)\) are given in Table 1. Then the independent fixed geodetic number of \(G\) is \(g_{if}(G) = min\left\{g_s(G)\right\} = 1\) and the \(g_{if}\)-sets of \(G\) are \(\{u_1\},\{u_2\}\) and \(\{u_3\}\).
| Independent set \(S\) | Minimum \(S\)-fixed geodetic sets | \(S\)-fixed geodeticnumber \(g_s(G)\) |
|---|---|---|
| \(\{u_1\}\) | \(\{u_2, u_3, u_5\}\) | \(3\) |
| \(\{u_2\}\) | \(\{u_3,u_5\}\) | \(2\) |
| \(\{u_3\}\) | \(\{u_2,u_5\}\) | \(2\) |
| \(\{u_4\}\) | \(\{u_1,u_2,u_3,u_5\}\) | \(4\) |
| \(\{u_5\}\) | \(\{u_1,u_2,u_3\}\) | \(3\) |
| \(\{u_1,u_5\}\) | \(\{u_2,u_3\}\) | \(2\) |
| \(\{u_2,u_3\}\) | \(\{u_1, u_5\}\) | \(2\) |
| \(\{u_2,u_5\}\) | \(\{u_3\}\) | \(1\) |
| \(\{u_3,u_5\}\) | \(\{u_2\}\) | \(1\) |
| \(\{u_2,u_3,u_5\}\) | \(\{u_1\}\) | \(1\) |
Theorem 2.3. Let \(S\) be an independent set of a connected graph \(G\).
(i) Every simplicial vertex in \(V-S\) belongs to every \(S\)-fixed geodetic set of \(G\).
(ii) No cut-vertex of \(G\) belongs to any minimum \(S\)-fixed geodetic set of \(G\).
Proof. Let \(S\) be an independent set of \(G\).
(i) Let \(u\) be a simplicial vertex in \(V-S\) and let \(S'\) be an \(S\)-fixed geodetic set of \(G\). If \(u\notin S'\), then \(u\) is an internal vertex of an \(x-y\) geodesic, say \(P\), for some element \(x\in S\) and for some element \(y\in S'\). Let \(v\) and \(w\) be the neighbours of \(u\) on \(P\). Then \(v\) and \(w\) are not adjacent in \(G\) and so \(u\) is not a simplicial vertex of \(G\), which is a contradiction.
(ii) Let \(v\) be a cut-vertex of \(G\). Then by Theorem 1.1, there exists a partition of the set of vertices \(V-\left\{v\right\}\) into subsets \(U\) and \(W\) such that for any vertex \(u\in U\) and \(w\in W\), the vertex \(v\) lies on every \(u-w\) path. Let \(S'\) be a minimum \(S\)-fixed geodetic set of \(G\). If \(v\in S\), then by the definition, \(v\notin S'\). Let \(v\in V-S\). Then \(S\cap U \neq \phi\) or \(S\cap W \neq \phi\). If \(S \cap U \neq \phi\), then let \(x\in S \cap U\). Now, claim that \(S' \cap W \neq \phi\). If \(S' \cap W =\phi\), then let \(w_1\in W\). Since \(S'\) is an \(S\)-fixed geodetic set, there exists an element \(y\) in \(S'\) such that \(w_1\) lies on an \(x-y\) geodesic \(P:x = x_0,x_1,\ldots,w_1,\ldots,x_n = y\) in \(G\). Then the \(x-w_1\) subpath of \(P\) and \(w_1-y\) subpath of \(P\) both contain \(v\) and so \(P\) is not an \(x-y\) path in \(G\). Hence \(S' \cap W \neq \phi\). Let \(w_2 \in S' \cap W\). Then \(v\) is an internal vertex of an \(x-w_2\) geodesic. Hence every vertex lying on an \(x-v\) geodesic also lies on an \(x-w_2\) geodesic and so \(S'' = S'-\{v\}\) is an \(S\)-fixed geodetic set of \(G\), which is a contradiction to \(S'\), a minimum \(S\)-fixed geodetic set of \(G\). Thus \(v\) does not belong to any minimum \(S\)-fixed geodetic set of \(G\). Similarly, if \(S \cap W \neq \phi\), then \(v\) does not belong to any minimum \(S\)-fixed geodetic set of \(G\). ◻
Corollary 2.4. No cut-vertex of \(G\) belongs to any \(g_{if}\)-set of \(G\).
Theorem 2.5.
(i) For the complete graph \(K_p\) (\(p\geq 2\)), \(g_{if}(K_p)={p-1}\).
(ii) For any non-trivial tree \(T\), \(g_{if}(T) = 1\).
(iii) For any cycle \(C_p\), \(g_{if}(C_p)\) = 1 or 2 according as \(p\) is even or odd.
(iv) For the wheel \(W_p = K_1 + C_{p – 1}\) (\(p \geq 5\)), \(g_{if}(W_p) = \left\lceil \frac{p-1}{4}\right\rceil\).
Proof. (i) For the complete graph \(K_p\), any single point set is a maximum independent set. Let \(S = \{x\}\) be an independent set of \(K_p\). Then by Theorem 2.3\((i)\), \(S' = V-S\) is a minimum \(S\)-fixed geodetic set of \(K_p\) and so \(g_{if}(K_p) = {p-1}\).
(ii) Let \(S_1 = \{x_1,x_2,\ldots,x_n\}\) be the set of all end vertices of \(T\). Then \(S = S_1-\{x_1\}\) is an independent set of \(T\). By Theorem 2.3, \(S' = \{x_1\}\) is an \(S\)-fixed geodetic set of \(T\) and so \(g_{if}(T) = 1\).
(iii) Let \(x\) be any vertex of an even cycle \(C_p\) and let \(y\) be the antipodal vertex of \(x\) in \(C_p\). It is clear that \(S = \{x\}\) is an independent set of \(C_p\) and \(S' = \{y\}\) is an \(S\)-fixed geodetic set of \(C_p\). Hence \(g_{if}(C_p)\) = 1.
Let \(C_p\) be an odd cycle and let \(S\) be an independent set of \(C_p\). It is clear that \(S\) contains atmost \(\frac{p-1}{2}\) non-adjacent vertices of \(C_p\). Let \(v\) be any vertex in \(V-S\). It is clear that every vertex of \(C_p\) do not lie on a \(u-v\) geodesic for some \(u\in S\). Hence a single point set of \(C_p\) will not form an \(S\)-fixed geodetic set of \(C_p\). Let \(x\in S\) and let \(y,z\) be the antipodal vertices of \(x\) in \(C_p\). Then every vertex of \(C_p\) lie either on an \(x-y\) geodesic or on an \(x-z\) geodesic. Hence \(S' = \{y, z\}\) is a minimum \(S\)-fixed geodetic set of \(C_p\) and so \(g_{if}(C_p) = 2\).
(iv) Let \(C: x_1, x_2,\ldots, x_{p-1}, x_1\) be the cycle in \(W_p\) and let \(x\) be the vertex of \(K_1\) in \(W_p\). Since the diameter of \(W_p\) is 2, the length of any geodesic is atmost 2. Hence we take an independent set \(S = \{x_1,x_5,x_9,\ldots,x_{4l+1}\}\), where \(l = \left\lfloor \frac{p-3}{4}\right\rfloor\). Let \(k = \left\lfloor \frac{p}{4}\right\rfloor\) and let \(S_1 = \{x_3,x_7,\ldots,x_{4k-1}\}\). If \(p = 4k\) or \(4k+1\), then let \(S' = S_1\); if \(p = 4k+2\), then let \(S' = S_1\cup \{x_{4k}\}\); and if \(p = 4k+3\), then let \(S' = S_1\cup \{x_{4k+2}\}\). It can be easily verified that \(S'\) is an \(S\)-fixed geodetic set of \(W_p\) and also \(S'\) is a \(g_{if}\)-set of \(W_p\). Hence \(g_{if}(W_p) = \left\lceil \frac{p-1}{4}\right\rceil\). ◻
Theorem 2.6. Let \(G\) be a bipartite graph with the partite sets \(V_1\) and \(V_2\). If the degree of every vertex in \(G\) is atleast 2 and if there exists a vertex \(x\) in \(V_1\) with \(deg~x = |V_2|\) or \(y\) in \(V_2\) with \(deg~y = |V_1|\), then \(g_{if}(G) = 1\).
Proof. Let \(V_1\) and \(V_2\) be the partite sets of a bipartite graph \(G\) with the degree of every vertex in \(G\) is atleast 2. If \(x\in V_1\) and \(deg~x = |V_2|\), then let \(S = V_1 – \{x\}\) and \(S' = \{x\}\). It is clear that every vertex of \(G\) lies on a \(u-x\) geodesic for some \(u\in S\) and so \(S'\) is the unique \(S\)-fixed geodetic set of \(G\). It follows that \(g_{if}(G) = 1\). Similarly, if \(y\in V_2\) and \(deg~y = |V_1|\), then \(S_1' = \{y\}\) is the unique \(S_1 = V_2-\{y\}\) fixed geodetic set of \(G\) and so \(g_{if}(G) = 1\). ◻
Corollary 2.7. If \(K_{m,n}\) is a complete bipartite graph, then \(g_{if}(K_{m,n}) = 1\).
Proof. The result follows from Theorems 2.5 (ii) and 2.6. ◻
Theorem 2.8. If \(G = K_1 + \bigcup m_jK_j\) with \(\sum m_j \geq 2\), then \(g_{if}(G) = \sum m_j(j-1)\).
Proof. Since \(\sum m_j\geq 2\), \(G = K_1 + \cup m_jK_j\) contains exactly one cut-vertex and all the remaining vertices are simplicial vertices. Let \(v\) be the cut-vertex of \(G\). Then \(G-v\) is a disconnected graph having exactly \(\sum m_j\) components and each component is complete. Let \(S\) be the collection of exactly one simplicial vertex from each component of \(G-v\). Clearly \(S\) is the maximal independent set of \(G\). Then by Theorem 2.3, \(V(G)-(S\cup\{v\})\) is the unique minimum \(S\)-fixed geodetic set of \(G\) and so \(g_s(G) = \sum m_j(j-1)\). Since \(S\) is the unique maximum independent set of \(G\), we have \(g_{if}(G) = \sum m_j(j-1)\). ◻
Note 2.9. In Theorem 2.8, if \(\sum m_j = 1\), then \(G = K_1 + K_j = K_{j+1}\). Then by Theorem 2.5(i), \(g_{if}(G) = {p-1} = j\).
The following result is clear from the definition.
Theorem 2.10. For any connected graph \(G\), \(1\leq g_{if}(G) \leq {p-1}\).
Remark 2.11. The bounds for \(g_{if}(G)\) in Theorem 2.10 are sharp. For any tree \(T\), \(g_{if}(T) = 1\) and for the complete graph \(K_p\), \(g_{if}(K_p) = {p-1}\).
Now we proceed to characterize graphs for which the upper bound in Theorem 2.10 is attained.
Theorem 2.12. For any connected graph \(G\) of order \(p\geq 2\), \(g_{if}(G) = {p-1}\) if and only if \(G = K_p\).
Proof. Let \(g_{if}(G) = {p-1}\). Then there is an independent set \(S\) containing exactly one vertex, say \(x\), and the \(S\)-fixed geodetic set \(S' = {V(G) – \{x\}}\). Hence no vertex of \(G\) is an internal vertex of any \(x-y\) geodesic for every vertex \(y\in S'\). That is, for any vertex \(y\in S'\), \(xy\) is an edge in \(G\). Now claim that for any two vertices \(u\) and \(v\) in \(S'\), \(uv\) is an edge in \(G\). If not, then \(d(u, v)\geq 2\) and let \(P: u = u_0,u_1,u_2,\ldots,u_n = v\) be a \(u-v\) geodesic in \(G\). Let \(S_1 = \{u\}\) and let \(S_1' = V(G)-\{u, u_1,u_2,\ldots,u_{n-1}\}\). Clearly \(S_1\) is an independent set of \(G\) and \(S_1'\) is an \(S_1\)-fixed geodetic set of \(G\). Hence \(g_{S_1}(G)\leq {p-2}\) and so \(g_{if}(G)\leq {p-2}\), which is a contradiction. Hence any two vertices in \(G\) are adjacent and so \(G = K_p\). Converse is clear from Theorem 2.5\((i)\). ◻
Theorem 2.13. For any connected graph \(G\) of order \(p\geq 3\), \(g_{if}(G) = {p-2}\) if and only if \(G = P_3\).
Proof. Let \(g_{if}(G) = {p-2}\). If \(G = K_p\), then by Theorem 2.12, \(g_{if}(G) = {p-1}\), which is a contradiction. Hence \(G\neq K_p\). If \(p=3\), then \(G = P_3\) has the desired properties. Now, let \(p\geq 4\). Since \(G\neq K_p\), there exist two vertices, say \(x\) and \(y\), in \(G\) such that \(d(x, y)\geq 2\). Let \(P: x=x_0,x_1,x_2,\ldots,x_n=y\) be an \(x-y\) geodesic in \(G\).
Case i. \(d(x,y)=2\). Since \(p\geq 4\) there exists another vertex \(z\), which is adjacent to either \(x,x_1\) or \(y\). If \(z\) is adjacent to both \(x\) and \(y\) in \(G\), then \(x_1\) and \(z\) lie on an \(x-y\) geodesic. Then \(S = \{x\}\) is an independent set and \(S' = V(G) – \{x, x_1, z\}\) is an \(S\)-fixed geodetic set of \(G\) and so \(g_{if}(G)\leq {p-3}\), which is a contradiction. If \(z\) is not adjacent to \(x\) or \(y\), then \(x_1\) lies on an \(x-z\) geodesic or on an \(y-z\) geodesic. Then \(S_1 = \{x, y\}\) is an independent set and \(S_1' = V(G) – \{x, y, x_1\}\) is an \(S_1\)-fixed geodetic set of \(G\) and so \(g_{if}(G)\leq {p-3}\), which is a contradiction.
Case ii. \(d(x,y)>2\). Clearly \(S = \{x\}\) is an independent set and \(S'= \left(V(G) – V(P)\right) \cup \{y\}\) is an \(S\)-fixed geodetic set of \(G\) and so \(g_{if}(G) \leq {p-3}\), which is a contradiction.
Conversely, let \(G = P_3\). Then by Theorem 2.5\((ii)\), \(g_{if}(G) = 1 = {p-2}\). ◻
Now we proceed to characterize graphs for which the lower bound in Theorem 2.10 is attained. For that we introduce the following definition.
Definition 2.14. Let \(G\) be a connected graph of order atleast 2. Let \(S\subset V(G)\) and \(y\in V(G)-S\). The distance between the set \(S\) and the vertex \(y\) is \(d(S, y) = min \{d(x, y): x\in S\}\). The eccentricity of the set \(S\) is \(e(S) = max \{d(S, y): y\in V(G)-S\}\). A vertex \(v\) of \(G\) such that \(d(S, v) = e(S)\) is called an eccentric vertex of \(S\).
Consider the graph \(G\) given in Figure 2. For the set \(S = \{x,u,v\}\), \(d(S,y) = 1\), \(d(S,z) = 1\), \(d(S, w) = 2\) and so \(e(S) = 2\). Similarly, for the independent set \(S_1 = \{x, v\}\), the distances from \(S_1\) are \(d(S_1, u) = 1, d(S_1, y) = 1, d(S_1, z) = 1\) and \(d(S_1, w) = 2\). Hence \(e(S_1) = 2\) and the eccentric vertex of \(S_1\) is \(w\).
Theorem 2.15. Let \(G\) be a connected graph. Then \(g_{if}(G) = 1\) if and only if there is an independent set \(S\) and its eccentric vertex \(y\) such that every vertex of \(G\) lies on an \(x-y\) geodesic for some \(x\in S\).
We have seen that if \(G\) is a connected graph of order \(p\geq 2\), then \(1\leq g_{if}(G)\leq {p-1}\). Also, we have the characterization results for \(g_{if}(G) = 1\), \({p-2}\) and \({p-1}\). In the following theorems we give some improved upper bounds for \(g_{if}(G)\) in terms of the vertex covering number \(\alpha(G)\), the vertex independence number \(\beta(G)\) and the vertex geodomination number \(g_x(G)\) of a graph \(G\).
Theorem 2.16. For any connected graph \(G\) of order \(p\), \(g_{if}(G)\leq {p-\beta(G)}\).
Proof. Let \(S\) be a maximum independent set of \(G\) and let \(S' = {V(G) – S}\). Then \(S'\) is an \(S\)-fixed geodetic set of \(G\) and so \(g_{if}(G)\leq |S'| = {p – \beta(G)}\). ◻
Corollary 2.17. If \(G\) is a connected graph with \(p\) vertices having no isolated vertices, then \(g_{if}(G)\leq \alpha(G)\).
Proof. The result follows from Theorems 1.2 and 2.16. ◻
Theorem 2.18. For any vertex \(x\) in a connected graph \(G\), \(g_{if}(G)\leq g_x(G)\).
Proof. Let \(x\) be any vertex and let \(S_x\) be the \(g_x\)-set of a connected graph \(G\). Let \(S = \{x\}\) and let \(S' = S_x\). It is clear that \(S'\) is an \(S\)-fixed geodetic set of \(G\) and hence \(g_{if}(G)\leq g_x(G)\). ◻
Remark 2.19. The bound of \(g_{if}(G)\) in Theorem 2.18 is sharp. For the complete graph \(G = K_p\), \(g_{if}(G) = g_x(G) = {p-1}\) for any vertex \(x\) in \(G\). Also, for the path \(G = P\), \(g_{if}(G) = g_x(G) = 1\) for any end vertex \(x\) in \(G\) and \(g_{if}(G) = 1< g_x(G)\) for any cut-vertex \(x\) in \(G\).
Corollary 2.20. If \(g_x(G) = 1\) for some vertex \(x\) in \(G\), then \(g_{if}(G) = 1\).
Theorem 2.21. If \(G\) is a connected graph of order \(p\) and diameter \(d\), then \(g_{if}(G)\leq {p-d}\).
Proof. Let \(P\) be a diametral path with end vertices \(x\) and \(y\) in \(G\). Let \(S = \{x\}\) and \(S' = \left(V(G)-V(P)\right)\cup\{y\}\). Since every vertex of \(P\) lies on an \(x-y\) geodesic, \(S'\) is an \(S\)-fixed geodetic set of \(G\) and so \(g_{if}(G)\leq {p-d}\). ◻
Remark 2.22. For the complete graph \(K_p\), diameter \(d = 1\) and \(g_{if}(G) = {p-1}\) so that the bound in Theorem 2.21 is sharp.
Theorem 2.23. For any non-trivial tree \(T\) of order \(p\) and diameter \(d\), \(g_{if}(T) = {p-d}\) if and only if \(T\) is a path.
Proof. Let \(g_{if}(T) = {p-d}\). If \(T\) is not a path, then the diameter \(d\) is less than or equal to \(p-2\) and so \({p-d}\geq 2\neq g_{if}(T)\), by Theorem 2.5\((ii)\), which is a contradiction. Conversely, if \(T\) is a path, then by Theorem 2.5\((ii)\), \(g_{if}(T) = 1 = {p-d}\). ◻
Theorem 2.24. There is no change in the independent fixed geodetic number by adding a pendant edge to a connected graph \(G\).
Proof. Let \(G'\) be the connected graph obtained from \(G\) by adding a pendant edge \(uv\), where \(u\) is a vertex of \(G\) and \(v\) is not a vertex of \(G\). Then \(u\) is a cut-vertex of \(G'\) and every vertex lying on a \(u-y\) geodesic also lies on a \(v-y\) geodesic for any \(y\neq u, v\) in \(G'\). Let \(S\) be an independent set and let \(S'\) be an \(S\)-fixed geodetic set of \(G\) with \(|S'|=g_{if}(G)\).
Case i. \(u\in S\). Since any vertex lying on a \(u-y\) geodesic also lies on a \(v-y\) geodesic for any \(y\) in \(S'\), we have \(S'\) is an \(S_1 = \left(S-\{u\}\right)\cup\{v\}\) fixed geodetic set of \(G'\) and so \(g_{if}(G') = g_{if}(G)\).
Case ii. \(u\in S'\). Then for any vertex \(x\in S\), the vertices in an \(x-u\) geodesic lie on an \(x-v\) geodesic and the vertices not in an \(x-u\) geodesic do not lie on any \(x-v\) geodesic in \(G'\). Hence \(S'' = \left(S'-\{u\}\right)\cup \{v\}\) is an \(S\)-fixed geodetic set of \(G'\). It follows that \(g_{if}(G') = g_{if}(G)\).
Case iii. \(u\notin S\cup S'\). Let \(S_1 = S\cup \{v\}\). Then \(S'\) is also an \(S_1\)-fixed geodetic set of \(G'\). Hence \(g_{if}(G') = g_{if}(G)\). ◻
We have proved that \(1\leq g_{if}(G)\leq {p-1}\) and \(g_{if}(G)\leq g_x(G)\) for any vertex \(x\) in a connected graph \(G\). By Theorem 1.3, it follows that \(1\leq g_x(G)\leq {p-1}\) for any vertex \(x\) in \(G\). Hence \(1\leq g_{if}(G)\leq g_x(G)\leq {p-1}\) for any vertex \(x\) in \(G\). The following theorem gives a realization for these parameters when \(1\leq a<b\leq {p-2}\).
Theorem 3.1. If \(a, b\) and \(p\) are positive integers such that \(1\leq a<b\leq {p-2}\), then there exists a connected graph \(G\) of order \(p\), \(g_{if}(G) = a\) and \(g_x(G) = b\) for some vertex \(x\) in \(G\).
Proof. Let \(P: w_1,w_2,\ldots,w_{p-b-1}\) be a path of order \(p-b-1\) and let \(K_{a+1}\) be the complete graph of order \(a+1\). Let \(H\) be a graph obtained from the path \(P\) and the complete graph \(K_{a+1}\) by joining the vertex \(w_{p-b-1}\) with every vertex of \(K_{a+1}\). Now, add \(b-a\) new vertices \(u_1,u_2,\ldots,u_{b-a}\) to the graph \(H\) and join each vertex \(u_i(1\leq i\leq {b-a})\) to the vertex \(w_1\) and obtain the graph \(G\) of Figure 3.
The graph \(G\) has order \(p\) and \(T = V(K_{a+1})\cup\{u_1,u_2,\ldots,u_{b-a}\}\) is the set of all simplicial vertices of \(G\). Let \(S = \{u_1,u_2,\ldots,u_{b-a},x\}\), where \(x\) is any vertex in \(K_{a+1}\). Let \(S' = V(K_{a+1})-\{x\}\). Then by Theorem 2.3\((i)\), \(S'\) is a subset of every \(S\)-fixed geodetic set of \(G\). It can be easily verified that \(S'\) itself is a \(S\)-fixed geodetic set of \(G\) and also \(S'\) is the unique \(g_{if}\)-set of \(G\). Hence \(g_{if}(G) = a\). Now, for the vertex \(x = u_1\), by Theorem 1.4, \(S_1 = T-\{u_1\}\) is a subset of any \(x\)-geodominating set of \(G\). Also, we can easily verify that \(S_1\) is the unique \(g_x\)-set of \(G\) and so \(g_x(G) = |S_1| = b\). Hence the result. ◻
Problem 3.2. If \(a,b\) and \(p\) are positive integers such that \(1\leq a = b\leq {p-2}\), does there exist a connected graph \(G\) of order \(p\), \(g_{if}(G) = a\) and \(g_x(G) = b\) for some vertex \(x\) in \(G~?\)
For every connected graph \(G\), \(rad~G\leq diam~G\leq 2~rad~G\). Ostrand [4] showed that any two positive integers \(a\) and \(b\) with \(a\leq b\leq 2a\) are realizable as the radius and diameter, respectively, of some connected graph. Ostrand’s theorem can be extended so that the independent fixed geodetic number can also be prescribed.
Theorem 3.3. For any three positive integers \(a, b\) and \(k\) with \(a\leq b\leq 2a\), there exists a connected graph \(G\) with \(rad~G = a\), \(diam~G = b\) and \(g_{if}(G) = k\).
Proof. We prove this theorem by considering two cases.
Case i. \(a = 1\). Then \(b = 1\) or \(2\). If \(b = 1\), then the complete graph \(G = K_{k+1}\) has the desired properties. Let \(b = 2\).
Subcase i. \(k = 1\). The path \(G = P_3\) has the desired properties.
Subcase ii. \(k\geq 2\). Construct a graph \(G\) by joining the vertex \(x\) of \(K_1\) with a vertex, say \(x_1\), of \(K_{k+2}\) and the graph \(G\) is shown in Figure 4. It is easily verified that \(e(x_1) = 1\) and \(e(y) = 2\) for any \(y\in V(G)-\{x_1\}\). Hence \(rad~G = 1\) and \(diam~G = 2\).
Let \(T = \left\{V(K_{k+2})-x_1\right\}\cup\{x\}\) be the set of all simplicial vertices of \(G\). Let \(S = \{x,y\}\), where \(y\in V(K_{k+2}) – \{x_1\}\), and let \(S' = T-S\). Then by Theorem 2.3\((i)\), \(S'\) is a subset of every \(S\)-fixed geodetic set of \(G\). It can be easily verified that \(S'\) is the unique \(g_{if}\)-set of \(G\) and so \(g_{if}(G) = k\).
Case ii. \(a\geq 2\).
Subcase i. \(a = b\). For \(k = 1\), let \(G = C_{2a}\). Then \(rad~G = diam~G = a\) and by Theorem 2.5\((iii)\), \(g_{if}(G) = 1\). Now, let \(k\geq 2\). Let \(C_{2a}:u_1,u_2,\ldots,u_{2a},u_1\) be a cycle of order \(2a\) and let \(K_{k+2}\) be the complete graph with the vertex set \(\{v_1,v_2,\ldots,v_{k+2}\}\). Let \(G\) be the graph obtained from \(C_{2a}\) and \(K_{k+2}\) by identifying the edge \(u_1u_2\) of \(C_{2a}\) with the edge \(v_1v_2\) of \(K_{k+2}\). The graph \(G\) is shown in Figure 5.
It can be easily verified that the eccentricity of any vertex in \(G\) is \(a\) so that \(rad~G = diam~G = a\). Let \(T = \{v_3,v_4,\ldots,v_{k+2}\}\) be the set of all simplicial vertices of \(G\). Let \(S = \{v_3,u_{a+1}\}\) and \(S' = T-\{v_3\}\). Then by Theorem 2.3\((i)\), \(S'\) is a subset of every \(S\)-fixed geodetic set of \(G\). Clearly, the vertices \(u_2,u_3,\ldots,u_a\) lie on a \(u_{a+1}-y\) geodesic for any \(y\in S'\) and the vertex \(u_i({a+2}\leq i\leq {2a}\)) does not lie on any \(x-y\) geodesic for any \(x\in S\) and \(y\in S'\). Hence \(S'\) is not an \(S\)-fixed geodetic set of \(G\). Let \(S'' = S'\cup \left\{u_{a+2}\right\}\). Now the vertices \(u_{a+3},u_{a+4},\ldots,u_{2a}\) and \(u_1\) lie on a \(v_3-u_{a+2}\) geodesic. Hence \(S''\) is an \(S\)-fixed geodetic set of \(G\). Also, it can be easily verified that \(S''\) is a \(g_{if}\)-set of \(G\) and so \(g_{if}(G) = |S''| = k\).
Subcase ii. \(a< b\leq 2a\). Let \(C_{2a}:u_1,u_2,\ldots,u_{2a}\) be a cycle of order \(2a\), let \(P_{b-a}: w_0,w_1,w_2,\ldots,w_{b-a-1}\) be a path of order \({b-a}\), and let \(K_{k+1}\) be the complete graph with the vertex set \(\{v_1,v_2,\ldots,v_{k+1}\}\). Let \(G\) be the graph obtained from \(C_{2a}\), \(P_{b-a}\) and \(K_{k+1}\) by \((i)\) identifying \(u_1\) of \(C_{2a}\) and \(w_0\) of \(P_{b-a+1}\) and \((ii)\) joining \(w_{b-a-1}\) with every vertex of \(K_{k+1}\). The graph \(G\) is shown in Figure 6. Then \(a\leq e(x)\leq b\) for any vertex \(x\) in \(G\), \(e(u_1) = a\), \(e(u_{a+1}) = b\) and so \(rad~G = a\) and \(diam~G = b\). Let \(S = \{u_{a+1}, v_1\}\) and let \(S' = V(K_{k+1}) – \{v_1\}\). It can be easily verified that \(S'\) is the unique \(S\)-fixed geodetic set of \(G\) and also \(S'\) is a \(g_{if}\)-set of \(G\). Thus \(g_{if}(G) = k\). ◻
Theorem 3.4. If \(p,d\) and \(n\) are positive integers such that \(3\leq d\leq {p-1}\), \(1\leq n\leq {p-1}\), and \(p-d-n-1\geq 0\), then there exists a graph \(G\) of order \(p\), diameter \(d\) and \(g_{if}(G) = n\).
Proof. Let \(P_d: u_0,u_1,u_2,\ldots,u_{d-1}\) be a path of order \(d\) and let \(K_{n+1}\) be a complete graph of order \(n+1\). Let \(H\) be a graph obtained from \(P_d\) and \(K_{n+1}\) by joining the vertex \(u_{d-1}\) to every vertex in \(K_{n+1}\). Now, add \({p-d-n-1}\) new vertices \(w_1,w_2,\ldots,w_{p-d-n-1}\) to \(H\) and join these to both \(u_0\) and \(u_2\), thereby producing the graph \(G\) of Figure 7.
Then \(G\) has order \(p\) and diameter \(d\). Let \(T = V(K_{n+1})\) be the set of all simplicial vertices of \(G\). Let \(S = \{u_0,x\}\), where \(x\) is any vertex in \(K_{n+1}\), and let \(S' = V(K_{n+1})-\{x\}\). Then by Theorem 2.3\((i)\), \(S'\) is a subset of every \(S\)-fixed geodetic set of \(G\). Also \(S'\) is the unique \(g_{if}\)-set of \(G\) and so \(g_{if}(G) = n\). ◻
An algorithm is a set of unambiguous instructions or procedures used for solving a given problem to provide correct and expected outputs for all valid and legal input data. Here we intend to provide two algorithms to find out \(g_{if}(G)\), i.e., to find the independent fixed geodetic number of \(G\). Algorithm 1 provides a method to find \(d(x,y)\), the distance between any two vertices. Algorithm 2 is a tool to determine the independent fixed geodetic number of \(G\).
Input: A graph \(G\) with vertex set \(V\) and edge set \(E\)
Output: Distance \(d(x,y)\) for any two vertices \(x\) and \(y\)
1. Let \(x, y\in V\)
2. \(S\gets \{x\}\) and \(c\gets 0\)
3. If \(x = y\), then go to step \(8\)
4. \(S'\gets V-S\) and \(T\gets \phi\)
5. For any vertex \(v\in S'\), if \(uv \in E\) for some \(u\in S\), then \(T\gets T\cup \{v\}\)
6. \(S\gets S\cup T\) and \(c\gets c + 1\)
7. If \(y\notin T\), then go to step \(4\)
8. Print \(d(x,y) = c\).
Input: A graph \(G\) with vertex set \(V\) having \(p\) vertices and edge set \(E\) having \(q\) edges
Output: Independent fixed geodetic number \(g_{if}(G)\)
1. \(g_{if}(G)\gets p – 1\)
2. for \(k = 1\) to \(p – 1\)
begin
3. for \(i = 1\) to \(\binom{p}{k}\)
4. \(j\gets 0\)
begin
5. Let \(S_i\) be a subset of \(V\) with \(k\) vertices
6. If \(d(u, v)\neq 1\) for any two vertices \(u, v\in S_i\), then
begin
\(j\gets j + 1\) and \(T_j\gets S_i\)
7. for \(l = 1\) to \(|V – T_j|\)
begin
8. for \(m = 1\) to \(\binom{|V – T_j|}{l}\)
begin
9. Let \(W_m\) be a subset of \(V – T_j\) with \(l\) vertices
10. \(I[T_j, W_m]\gets \phi\)
11. For any two vertices \(x\in T_j\) and \(y\in W_m\), if \(z\in V\) and
\(d(x, z) + d(z, y) = d(x, y)\), then \(I[T_j, W_m]\gets I[T_j, W_m]\cup \{z\}\)
12. If \(I[T_j, W_m] = V\), then \(g_{if}(G)\gets min\{g_{if}(G), l\}\)
13. If \(g_{if}(G) = 1\), then go to step \(14\)
end
end
end
end
end
14. Print: The independent fixed geodetic number of \(G\) is \(g_{if}(G)\).
In the independent fixed geodetic algorithm (IFG algorithm), initially the independent fixed geodetic number \(g_{if}(G)\) of a graph \(G\) is assigned a value equal to \(p – 1\). The complexity of IFG algorithm is mainly dominated by the nested for statements in lines \(2\) and \(4\), and they execute atmost \[\binom{p}{1} + \binom{p}{2} + . . . + \binom{p}{p-1} = 2^p-2,\] operations. Since the set \(S_i\) contains atmost \(p-1\) vertices, line \(6\) can be achieved with \[\binom{p-1}{2},\] comparisons. In addition, we have two more nested for statements in lines \(7\) and \(8\), and they execute atmost \[\binom{p-1}{1} + \binom{p-1}{2} + . . . + \binom{p-1}{p-1} = 2^{p-1}-1,\] times. Also, lines \(11\) and \(12\) requires not more than \(\binom{p-1}{2}2p\) assignments. Thus the total number of computations in IFG algorithm is atmost
\[\begin{aligned} &(2^p-2)\left[ \frac{(p-1)(p-2)}{2} + ({2^{p-1}-1})\frac{(p-1)(p-2)}{2}2p\right] \\&\qquad = p2^{2p}+ (p^3-3p^2)2^{2p-1}+ (3p^2-p^3-4p+1)2^p + {(7p^2-2p^3-3p)}2^{p-1}\\&\qquad\;\;+ 2p^3-7p^2+7p-2. \end{aligned}\]
Thus IFG algorithm can be implemented in \(O(n.log_2 n)\) time complexity where \(n = 2^{2p}\).
Dam could be compared to a mother who nurtures, cares and nourishes her children. Dam, a reservoir of water is built on a river basin or across a river or near water catchment area to confine water on upstream side. For this reason water in the dam gushes forth all through the year and it rarely dries. Though rain is the main source of water in the dam, springs around keep it always moisture. Dam is designed in such a way that water flows from upstream to downstream which ensures the safety and security of all living beings and their habitats. Flood control measures are being assured while constructing the dams. Dam being a recipient of rain water acts as a donor supplying water and promises freshness to the terrestrial life. It serves the purpose of irrigation, human consumption, industrial use, aquaculture and navigability. It is a main source of power generation where potential energy is converted into electrical energy. Water in the dam is evenly distributed to various locations according to the need with a proper planning and execution. Dam, a vessel of life and prosperity fructify the fields, plants, trees, animals and human beings as the stored water moves through canals. As the water flows through the canals, it continues to fill the ponds for the sustenance of the living beings around. Building of ponds are done in such a way that certain ponds are interconnected so that when one pond gets filled up, the excess water flows to the adjacent one. This partially fulfills the purpose of saving the excess water. This could be done systematically if we are able to identify the required number of ponds among the tail piece ponds and increase their water storage capacity.
Our concern here is to determine the minimum number of tail piece ponds, so that wastage of water is minimized. By increasing the storage capacity of the tail piece ponds, this is attained. For that purpose we constitute a graph where the vertices refer to dams and ponds, and the edges refer to the ways dams and ponds are connected to each other as well as the interconnecting paths between the ponds. Keeping the dams as the independent set \(S\), we try to find \(S'\subseteq V – S\), the suitable minimum number of tail piece ponds so that water is not wasted. There by the cardinality of \(S'\) is the required independent geodetic number \(g_{if}(G)\) in the graph \(G\). This determines the minimum number of tail piece ponds whose storage capacity to be increased in order to minimize the wastage of water.