Independent Fixed Connected Geodetic Number of a Graph

Titus, P.; Mary, S.

doi:/10.61091/ars157-11

Abstract

1. Introduction
2. Independent fixed connected geodetic number
3. Connected Geo-independent Number
Conflict of Interest

References

Ars Combinatoria

Volume 157
Pages: 109-120

Research article

Independent Fixed Connected Geodetic Number of a Graph

^¹, ^²

¹Department of Mathematics, University College of Engineering Nagercoil, Anna University, Tirunelveli Region.

²Department of Mathematics,Holy Cross College (Autonomous), Nagercoil, India.

Received: 12/12/2023
Accepted: 21/12/2023
Published: 25/12/2023

Copyright Link
License

Abstract

In this paper we introduce the concept of independent fixed connected geodetic number and investigate its behaviours on some standard graphs. Lower and upper bounds are found for the above number and we characterize the suitable graphs achieving these bounds. We also define two new parameters connected geo-independent number and upper connected geo-independent number of a graph. Few characterization and realization results are formulated for the new parameters. Finally an open problem is posed.

Keywords: Independent fixed connected geodetic set, Independent fixed connected geodetic number, Connected Geo-independent number, Upper connected Geo-independent number

1. Introduction

The introduction of Graph Theory is a revolution in the field of Mathematics. Various concepts were made easily understandable by its simple expression through graphical models. By a graph $G$ we mean $V$ , the set of vertices; $E$ , the set of edges together with a binary operation of association. We refer to [1,2, 3 ] for basic graph theoretic terms. In $G$ , a shortest $x - y$ path is also known as $x - y$ geodesic. The distance $d (x, y)$ is defined as the number of edges of an $x - y$ geodesic in $G$ . For any two vertices $x$ and $y$ in $G$ , the closed interval $I [x, y]$ is the collection of vertices on an $x - y$ geodesic. The closed interval $I [S, S^{'}]$ , where $S, S^{'} \subseteq V (G)$ , is defined as the union of subintervals $I [x, y]$ for some $x \in S$ and $y \in S^{'}$ . i.e., $I [S, S^{'}] = ⋃_{x \in S, y \in S^{'}} I [x, y]$ . A vertex $v$ in $G$ is called an extreme vertex or simplicial vertex if the subgraph induced by its adjacent vertices is complete.

A set $S \subseteq V (G)$ is called a geodetic set or geodomination set if every vertex of $G$ is on some $x - y$ geodesic where $x, y \in S$ . The minimum cardinality of a geodetic set of $G$ is called as the geodetic number of $G$ , denoted by $g (G)$ [4, 5, 6, 7, 8]. If $S$ is a geodetic set of $G$ and $⟨ S ⟩$ is connected, then $S$ is called the connected geodetic set of $G$ . Its minimum order is named as the connected geodetic number of $G$ , denoted by $c g (G)$ . A connected geodetic set of cardinality $c g (G)$ is called a $c g$ -set of $G$ [9]. Again parameters upper connected geodetic number and forcing connected geodetic number were defined and investigated in [10]. Santhakumaran and Titus first introduced the vertex geodomination number in [11] and further studied in [12, 13]. For any vertex $x$ in $G$ , a set $S \subseteq V (G)$ is called an $x$ -geodominating set of $G$ if every vertex $v$ in $G$ is on an $x - y$ geodesic for some $y$ in $S$ . The minimum cardinality of an $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 of $G$ . A connected $x$ -geodominating set of $G$ is an $x$ -geodominating set $S$ such that $⟨ S ⟩$ is connected. The minimum cardinality of a connected $x$ -geodominating set of $G$ is the connected $x$ -geodomination number of $G$ and is denoted by $c g_{x} (G)$ . A connected $x$ -geodominating set of cardinality $c g_{x} (G)$ is called a $c g_{x}$ -set of $G$ [14].

Let $e = x y$ be any edge of a connected graph $G$ of order atleast 3. A set $S$ of vertices of $G$ is an $e$ -geodominating set of $G$ if every vertex of $G$ is either on an $x - u$ geodesic or on an $y - u$ geodesic for some element $u$ in $S$ . The minimum cardinality of an $e$ -geodominating set of $G$ is defined as the $e$ -geodomination number of $G$ and is denoted by $g_{e} (G)$ or $g_{x y} (G)$ . An $e$ -geodominating set of cardinality $g_{e} (G)$ is called a $g_{e}$ -set of $G$ [15].

It is clear that $x$ -geodominating set of $G$ is obtained by fixing a vertex $x$ in $G$ and $e$ -geodominating set of $G$ is obtained by fixing an edge $e = x y$ in $G$ . Based on these concepts we defined a new parameter called independent fixed geodomination number (or independent fixed geodetic number) in [16]. Let $S$ be an independent set of a connected graph $G$ of order atleast $2$ . Let $S^{'}$ be a subset of $V (G)$ . If each vertex $v$ in $G$ is on an $x - y$ geodesic for some $x \in S$ and $y \in S^{'}$ , then $S^{'}$ is an $S$ -fixed geodetic set of $G$ . 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_{i f} (G) = m i n {g_{s} (G)}$ , where the minimum is taken over all independent sets $S$ in $G$ . An independent fixed geodetic set of cardinality $g_{i f} (G)$ is described as $g_{i f}$ -set of $G$ . We too further proceed to infer about connectedness of an $S$ -fixed geodetic set of $G$ , where $S$ is an independent set in a connected graph $G$ . In the computation of independent fixed connected geodetic number, the succeeding theorems will be employed.

Theorem 1. [16] For any connected graph $G$ , $1 \leq g_{i f} (G) \leq p - 1$ .

Theorem 2. [16] Let $G$ be a connected graph. Then $g_{i f} (G) = 1$ if and only if there is an independent set $S$ and its eccentric vertex $y$ such that every vertex of $G$ is on an $x - y$ geodesic for some $x \in S$ .

Theorem 3. [16] For any complete graph $K_{p}$ , $g_{i f} (K_{p}) = p - 1$ .

2. Independent fixed connected geodetic number

Definition 1. Let $S$ be an independent set of a connected graph $G$ of order atleast 2. An $S$ -fixed connected geodetic set of $G$ is an $S$ -fixed geodetic set $S^{'}$ such that $⟨ S^{'} ⟩$ is connected. The $S$ -fixed connected geodetic number $c g_{s} (G)$ of $G$ is the minimum cardinality of an $S$ -fixed connected geodetic set of $G$ . The independent fixed connected geodetic number $c g_{i f} (G)$ of $G$ is defined as $c g_{i f} (G) = m i n {c g_{s} (G)}$ , where the minimum is taken over all independent sets $S$ in $G$ . An independent fixed connected geodetic set of cardinality $c g_{i f} (G)$ is called a $c g_{i f}$ -set of G.

Example 1. Consider a graph $G$ as shown in Figure 1. The Table 1 gives the independent sets $S$ , their corresponding minimum $S$ -fixed geodetic sets and minimum $S$ -fixed connected geodetic sets, the $S$ -fixed geodetic numbers $g_{s} (G)$ and the $S$ -fixed connected geodetic numbers $c g_{s} (G)$ . Then the independent fixed geodetic number of $G$ is $g_{i f} (G) = m i n {g_{s} (G)} = 2$ and the independent fixed connected geodetic number of $G$ is $c g_{i f} (G) = m i n {c g_{s} (G)} = 3$ .

Table 2.1
Independent	Minimum $S$ -fixed	$S$ -fixed	Minimum $S$ -fixed	$S$ -fixed
set $S$	geodetic set	geodetic	connected geodetic set	connected
		number $g_{s} G$		geodetic
				number $c g_{s} G$
${x_{1}}$	${x_{2}, x_{4}, x_{5}, x_{6}}$	$4$	${x_{2}, x_{3}, x_{4}, x_{5}, x_{6}}$	$5$
${x_{2}}$	${x_{1}, x_{4}, x_{5}, x_{6}}$	$4$	${x_{1}, x_{3}, x_{4}, x_{5}, x_{6}}$	$5$
${x_{3}}$	${x_{1}, x_{2}, x_{4}, x_{5}, x_{6}}$	$5$	${x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}}$	$6$
${x_{4}}$	${x_{1}, x_{2}, x_{6}}$	$3$	${x_{1}, x_{2}, x_{3}, x_{6}}$	$4$
${x_{5}}$	${x_{1}, x_{2}, x_{4}, x_{6}}$	$4$	${x_{1}, x_{2}, x_{3}, x_{4}, x_{6}}$	$5$
${x_{6}}$	${x_{1}, x_{2}, x_{4}}$	$3$	${x_{1}, x_{2}, x_{3}, x_{4}}$	$4$
${x_{1}, x_{4}}$	${x_{2}, x_{6}}$	$2$	${x_{2}, x_{3}, x_{6}}$	$3$
${x_{1}, x_{5}}$	${x_{2}, x_{4}, x_{6}}$	$3$	${x_{2}, x_{3}, x_{4}, x_{6}}$	$4$
${x_{1}, x_{6}}$	${x_{2}, x_{4}}$	$2$	${x_{2}, x_{3}, x_{4}}$	$3$
${x_{2}, x_{4}}$	${x_{1}, x_{6}}$	$2$	${x_{1}, x_{3}, x_{6}}$	$3$
${x_{2}, x_{5}}$	${x_{1}, x_{4}, x_{6}}$	$3$	${x_{1}, x_{3}, x_{4}, x_{6}}$	$4$
${x_{2}, x_{6}}$	${x_{1}, x_{4}}$	$2$	${x_{1}, x_{3}, x_{4}}$	$3$
${x_{4}, x_{6}}$	${x_{1}, x_{2}, x_{5}}$	$3$	${x_{1}, x_{2}, x_{3}, x_{5}}$	$4$
${x_{1}, x_{4}, x_{6}}$	${x_{2}, x_{5}}$	$2$	${x_{2}, x_{3}, x_{5}}$	$3$
${x_{2}, x_{4}, x_{6}}$	${x_{1}, x_{5}}$	$2$	${x_{1}, x_{3}, x_{5}}$	$3$

Theorem 4. In a connected graph $G$ , $1 \leq g_{i f} (G) \leq c g_{i f} (G) \leq p - 1$ .

Proof. For any independent set $S$ in a connected graph $G$ , every $S$ -fixed connected geodetic set is an $S$ -fixed geodetic set of $G$ , we have $g_{i f} (G) \leq c g_{i f} (G)$ . Then by Theorem 1, we have $1 \leq g_{i f} (G) \leq c g_{i f} (G) \leq p - 1$ .

We intend to characterize the graphs that realize the bounds in Theorem 4. For that we use the following definition.

Definition 2. [16] 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) = m i n {d (x, y) : x \in S}$ . The eccentricity of the set $S$ is $e (S) = m a x {d (S, y) : y \in V (G) - S}$ . An eccentric vertex of $S$ is a vertex $v$ of $G$ with $d (S, v) = e (S)$ .

Theorem 5. Let $G$ be a connected graph of order atleast 2. Then $c g_{i f} (G) = 1$ if and only if there is an independent set $S$ and its eccentric vertex $y$ such that every vertex of $G$ is on an $x - y$ geodesic for some $x \in S$ .

Proof. The result follows from Theorems 2 and 4.

The following theorem gives $c g_{i f} (G)$ for some standard graphs.

Theorem 6.

If $G = T$ or $K_{m, n}$ , then $c g_{i f} (G) = 1$ .
If $G = C_{p}$ , then $c g_{i f} (G)$ is 1 or 2 according as $p$ is even or odd.
If $G = K_{1} + \cup m_{j} K_{j}$ with $G$ is neither a complete graph nor a star, then $c g_{i f} (G) = j - 1$ or $\sum m_{j} (j - 1) + 1$ according as $\sum_{j \geq 2} m_{j} = 1$ or $\sum_{j \geq 2} m_{j} \geq 2$ .

In view of Theorem 4, we proceed to characterize graphs $G$ with $c g_{i f} (G) = p - 1$ .

Theorem 7. Let $G$ be a connected graph of order $p \geq 2$ . Then $c g_{i f} (G) = p - 1$ if and only if $G = K_{p}$ .

Proof. Let $c g_{i f} (G) = p - 1$ . Claim that $G = K_{p}$ . If not, then $G$ has a diametral path $P : u_{0}, u_{1}, \dots, u_{d}$ of length $d \geq 2$ . It is clear that $u_{0}$ and $u_{d}$ are non-cut vertices of $G$ . If $u_{0}$ or $u_{d}$ is an end vertex of $G$ , then $S = {u_{0}, u_{d}}$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 2$ , but this leads to a contradiction. If both $u_{0}$ and $u_{d}$ are non-end vertices of $G$ , then there exist atleast two $u_{0} - u_{d}$ paths in $G$ . If atleast one vertex other than $u_{0}$ and $u_{d}$ is common for any two $u_{0} - u_{d}$ paths in $G$ , then $S = {u_{0}, u_{d}}$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 2$ , but this leads to a contradiction. Suppose that there exist two $u_{0} - u_{d}$ paths, say $P_{1}$ and $P_{2}$ , has no common vertices other than $u_{0}$ and $u_{d}$ . Let $z$ be an adjacent vertex of $u_{0}$ in $P_{1}$ . If $z$ is a cut vertex of $G$ , then let $H$ be a component of $G - z$ with $u_{0}$ not in $H$ . Let $z_{1}$ be a vertex farthest away from $z$ in $H$ . Then it is clear that $S = {z_{1}, u_{d}}$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 2$ , but this leads to a contradiction. If $z$ is not a cut vertex and ${u_{o}, z}$ is not a vertex-cut of $G$ , then $S = {u_{0}}$ is an independent set of $G$ and $S^{'} = V (G) - {u_{0}, z}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 2$ , but this leads to a contradiction. If $z$ is not a cut vertex and ${u_{0}, z}$ is a vertex-cut of $G$ , then there exists another $u_{0} - z$ path, say $Q$ , of length atleast 2. Let $w$ be an adjacent vertex of $u_{0}$ on $Q$ . If $w$ is a cut vertex of $G$ , then let $H_{1}$ be a component of $G - w$ with $u_{0}$ not in $H_{1}$ . Let $w_{1}$ be a vertex farthest away from $w$ in $H_{1}$ . Then it is clear that $S = {w_{1}, u_{d}}$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 2$ , but this leads to a contradiction. If $w$ is not a cut vertex and ${w, u_{d}}$ is not a vertex-cut of $G$ , then $S = {w, u_{d}}$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 2$ , but this leads to a contradiction. If $w$ is not a cut vertex and ${w, u_{d}}$ is a vertex-cut of $G$ , then $S = {w}$ is an independent set of $G$ and $S^{'} = V (G) - {w, u_{0}}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 2$ , but this leads to a contradiction. Converse is clear from Theorems 3 and 4.

Now we proceed to characterize graphs $G$ with $c g_{i f} (G) = p - 2$ . For that we require the definition of a special graph $K_{m} \leftarrow P_{r} \to K_{n}$ .

Definition 3. The graph $G = K_{m} \leftarrow P_{r} \to K_{n}$ is obtained from two complete graphs $K_{m}, K_{n}$ and a path $P_{r}$ by joining every vertex in $K_{m}$ with an end vertex of $P_{r}$ and joining every vertex in $K_{n}$ with the other end vertex of $P_{r}$ .

The graph $G = K_{m} \leftarrow P_{r} \to K_{n}$ is shown in Figure 2.

Theorem 8. Let $G$ be a connected graph of order $p \geq 3$ . Then $c g_{i f} (G) = p - 2$ if and only if $G$ is either $P_{3}$ or $K_{m} \leftarrow P_{r} \to K_{n}$ ( $m, n \geq 2$ and $r \geq 1$ ).

Proof. Let $c g_{i f} (G) = p - 2$ . If $p = 3$ , then by Theorems 7 and 6 $(i)$ we conclude that $G = P_{3}$ . If $p = 4$ , then $G$ is either $K_{4}, K_{2} + \bar{K_{2}}, K_{1} + (K_{1} \cup K_{2}), K_{1, 3}, P_{4}$ or $C_{4}$ . If $G = K_{4}$ , then by Theorem 7, $c g_{i f} (G) = 3 = p - 1$ , but this leads to a contradiction. If $G = K_{2} + \bar{K_{2}}$ , then $G$ has two simplicial vertices, say $x$ and $y$ . It is obvious that $S = {x}$ is an independent set of $G$ and $S^{'} = {y}$ is the minimum $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) = 1 = p - 3$ , but this leads to a contradiction. If $G = K_{1} + (K_{1} \cup K_{2}), K_{1, 3}, P_{4}$ or $C_{4}$ , then by Theorem 6, $c g_{i f} (G) = 1 = p - 3$ , but this leads to a contradiction.
Now, let $p \geq 5$ . Since $c g_{i f} (G) = p - 2$ , by Theorem 7, we have $G \neq K_{p}$ . First, we show that every vertex of $G$ is either a cut vertex or a simplicial vertex. Incase there exists a vertex, say $x$ , in $G$ which is neither a cut vertex nor a simplicial vertex, then $x$ lies on a cycle in $G$ . Let $C$ be a largest chordless cycle containing the vertex $x$ in $G$ . We consider three cases.
Case (1) Length of the cycle $C$ is more than 3 and degree of $x$ is 2.
Let $y$ and $z$ be the adjacent vertices of $x$ on $C$ . Since $C$ is a chordless cycle, $y$ and $z$ are non-simplicial vertices of $G$ .
Subcase (1) $d e g y = d e g z = 2$ . Let $S = {x}$ be an independent set of $G$ . If $C$ is an even cycle, then $y$ and $z$ is on an $x - x_{1}$ geodesic, where $x_{1}$ is an eccentric vertex of $x$ on $C$ ; and if $C$ is an odd cycle, then $y$ is on an $x - x_{1}$ geodesic and $z$ is on an $x - x_{2}$ geodesic, where $x_{1}$ and $x_{2}$ are the eccentric vertices of $x$ on $C$ . Then it is clear that $S^{'} = V (G) - {x, y, z}$ is an $S$ -fixed geodetic set of $G$ . Since $d e g y = d e g z = d e g x = 2$ , $⟨ S^{'} ⟩$ is connected. Hence $S^{'}$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
Subcase (2) $d e g y \geq 3$ and $d e g z \geq 3$ . Since $d e g x = 2$ , $G - x$ is a connected graph. If $y$ and $z$ are cut vertices of $G$ , then let $G_{1}$ and $G_{2}$ be the components of $G - y$ and $G - z$ , respectively, with the vertex $x$ not in both $G_{1}$ and $G_{2}$ . Let $y_{1}$ be a vertex farthest away from $y$ in $G_{1}$ and let $z_{1}$ be a vertex farthest away from $z$ in $G_{2}$ . Then it is vivid that $S = {x, y_{1}, z_{1}}$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
If $y$ and $z$ are non-cut vertices of $G$ and ${y, z}$ is a vertex-cut of $G - x$ , then $y, x$ and $z$ are the consecutive vertices of another chordless cycle, say $C^{'}$ , in $G$ . Let $z^{'} \neq x$ be an adjacent vertex of $z$ on $C^{'}$ . If $z^{'}$ is a non-cut vertex of $G$ , then $S = {x, z^{'}}$ is an independent set of $G$ and $S^{'} = V (G) - {x, z, z^{'}}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. If $z^{'}$ is a cut vertex of $G$ , then let $G_{3}$ be a component of $G - z^{'}$ with the vertex $z$ not in $G_{3}$ . Let $z^{″}$ be a vertex farthest away from $z^{'}$ in $G_{3}$ . Then $S_{1} = {x, z^{″}}$ is an independent set of $G$ and $S_{1}^{'} = V (G) - {x, z, z^{″}}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
If $y$ and $z$ are non-cut vertices of $G$ and ${y, z}$ is not a vertex-cut of $G - x$ . It is clear that $S = {x}$ is an independent set of $G$ and $S^{'} = V (G) - {x, y, z}$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. If either $y$ or $z$ is a cut vertex of $G$ , then by the arguments similar to the above, we get a contradiction.
Subcase (3) $d e g y = 2$ and $d e g z \geq 3$ ((or) $d e g y \geq 3$ and $d e g z = 2$ ). If $z$ is a cut vertex of $G$ , then let $G_{1}$ be a component of $G - z$ with the vertex $x$ not in $G_{1}$ . Let $z^{'}$ be a vertex farthest away from $z$ in $G_{1}$ . Then $S = {x, z^{'}}$ is an independent set of $G$ and $S^{'} = V (G) - {x, y, z^{'}}$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
If $z$ is not a cut vertex of $G$ , then clearly $S = {x}$ is an independent set of $G$ and $S^{'} = V (G) - {x, y, z}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
Case (2) Length of the cycle $C$ is more than 3 and degree of $x$ is more than 2.
Subcase (1) ${x, y}$ and ${x, z}$ are non vertex-cuts of $G$ . Then it is clear that $S = {x}$ is an independent set of $G$ and $S^{'} = V (G) - {x, y, z}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
Subcase (2) ${x, y}$ and ${x, z}$ are vertex-cuts of $G$ . Then $G$ has two more cycles, say $C_{1}$ and $C_{2}$ , with $x y$ an edge of $C_{1}$ and $x z$ an edge of $C_{2}$ . Let $x^{'} \neq y$ be an adjacent vertex of $x$ on $C_{1}$ and let $x^{″} \neq z$ be an adjacent vertex of $x$ on $C_{2}$ . If $x^{'}$ is a cut vertex of $G$ , then take $a = x_{1}^{'}$ , where $x_{1}^{'}$ is a vertex farthest away from $x^{'}$ in a component $H$ of $G - x^{'}$ with $x$ not a vertex of $H$ . Otherwise, take $a = x^{'}$ . Similarly, if $x^{″}$ is a cut vertex of $G$ , then take $b = x_{1}^{″}$ , where $x_{1}^{″}$ is a vertex farthest away from $x^{″}$ in a component $H_{1}$ of $G - x^{″}$ with $x$ not a vertex of $H_{1}$ . Otherwise, take $b = x^{″}$ . It is clear that $S = {a, b}$ is an independent set of $G$ and $S^{'} = V (G) - {x, a, b}$ is an $S$ -fixed connected geodetic set of $G$ . It implies $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
Subcase (3) ${x, y}$ is a vertex-cut and ${x, z}$ is not a vertex-cut of $G$ ((or) ${x, y}$ is not a vertex-cut and ${x, z}$ is a vertex-cut of $G$ ). Then $G$ has one more chordless cycle, say $C_{1}$ , with $x y$ an edge of $C_{1}$ . Let $x^{'} \neq y$ be an adjacent vertex of $x$ on $C_{1}$ . If $x^{'}$ is adjacent to $y$ in $G$ and $x^{'}$ is not a cut vertex of $G$ , then $S = {x^{'}}$ is an independent set of $G$ and $S^{'} = V (G) - {x, x^{'}, z}$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. If $x^{'}$ is adjacent to $y$ in $G$ and $x^{'}$ is a cut vertex of $G$ , then by an argument similar to Subcase (3) of Case (1), $S = {x, x^{″}}$ is an independent set of $G$ and $S^{'} = V (G) - {x, x^{″}, z}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
Similarly, if $x^{'}$ is a non-adjacent vertex of $y$ on $C_{1}$ and $x^{'}$ is a non-cut vertex of $G$ , then $S = {x}$ and $S^{'} = V (G) - {x, x^{'}, z}$ . If $x^{'}$ is a non-adjacent vertex of $y$ and $x^{'}$ is a cut vertex of $G$ , then $S = {x, x^{″}}$ and $S^{'} = V (G) - {x, x^{″}, z}$ , where $x^{″}$ is a vertex farthest away from $x^{'}$ in a component $H$ of $G - x^{'}$ with $x$ not a vertex of $H$ . In both cases, $S$ is an independent set of $G$ and $S^{'}$ is an $S$ -fixed connected geodetic set of $G$ and hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.
Case (3) Length of the cycle $C$ is 3.

Then the graph $H$ given in Figure 2.3 is a subgraph of $G$ . If not, every block of $G$ is either $K_{2}$ or $K_{3}$ and so every vertex of $G$ is either a cut vertex or a simplicial vertex, which is a contradiction to our assumption. Here we take the vertex $u$ as $x$ and the cycle $u, v, w, z, u$ in $H$ as $C$ and continue the procedure exactly similar to Case (1) and Case (2), we get $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction.

Hence in all the three cases we get a contradiction and so every vertex in $G$ is either a cut vertex or a simplicial vertex. Since $c g_{i f} (G) = p - 2$ , by Theorem 7, $G$ is a non-complete graph. Hence $G$ has atleast one cut vertex. Let $Q = {u_{1}, u_{2}, \dots, u_{a}}$ be the set of all cut vertices of $G$ . We consider two cases.
Case (1) $G$ has exactly one cut vertex, say $u_{1}$ .

Let $G_{1}, G_{2}, \dots, G_{t} (t \geq 2)$ be the components of $G - u_{1}$ . If $t \geq 3$ , then $S = {x_{1}, x_{2}, \dots, x_{t}}$ , where $x_{i} \in G_{i} (1 \leq i \leq t)$ , is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. Hence $t = 2$ . Now claim that each component $G_{i} (1 \leq i \leq 2)$ has atleast two vertices. If $G_{1}$ has exactly one vertex, say $v$ , then $S = {v, z}$ , where $z \in G_{2}$ , is an independent set of $G$ . It is clear that $S^{'} = V (G) - {v, z, u_{1}}$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. Hence $G$ has exactly one cut vertex and two components with each component having atleast two vertices. Hence $G = K_{m} \leftarrow P_{r} \to K_{n}$ ( $m, n \geq 2$ and $r = 1$ ).
Case (2) $G$ has two or more cut vertices.

Let $R = {z_{1}, z_{2}, \dots, z_{l}} (l \geq 0)$ be the set of all cut vertices of degree $\geq 3$ in $G$ . If $l = 0$ , then $G$ is a path and so by Theorem 6(i), $c g_{i f} (G) = 1 < p - 3$ , but this leads to a contradiction. Now, let $l \geq 1$ and let $S = {x_{1}, x_{2}, \dots, x_{b}}$ $(b \geq m a x {2, l})$ , where $x_{i}$ is a simplicial vertex of $G$ in the $i^{t h}$ component of $G - R$ . If $l \geq 3$ , then clearly $S$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. If $l = 1$ , then clearly $S$ is an independent set of $G$ and $S^{'} = V (G) - {S \cup (Q - R)}$ is an $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. Hence $l = 2$ . If $G - R$ has 3 or more components, then $S$ is an independent set of $G$ and $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \leq p - 3$ , but this leads to a contradiction. Hence $G - R$ has exactly 2 components. Since every vertex of $G$ is either a cut vertex or a simplicial vertex, the components of $G - R$ are complete graphs. Since $l = 2$ , the two components of $G - R$ are complete graphs with atleast two vertices and $⟨ R ⟩$ is a path. Hence $G = K_{m} \leftarrow P_{r} \to K_{n}$ ( $m, n \geq 2$ and $r \geq 1$ ).

Conversely, let $G = P_{3}$ or $K_{m} \leftarrow P_{r} \to K_{n}$ $(m, n \geq 2$ and $r \geq 1)$ . If $G = P_{3}$ , then by Theorem 6(i), $c g_{i f} (G) = 1 = p - 2$ . If $G = K_{m} \leftarrow P_{r} \to K_{n}$ , then every vertex in $K_{m} \cup K_{n}$ is a simplicial vertex of $G$ . It is clear that any independent set $S$ of $G$ contains atmost one vertex from each $K_{m}$ and $K_{n}$ . Also, every $S$ -fixed connected geodetic set of $G$ contains atleast $m - 1$ vertices from $K_{m}$ and atleast $n - 1$ vertices from $K_{n}$ . Since $m \geq 2$ , $n \geq 2$ and $r \geq 1$ , every vertex of $P_{r}$ is an element of any $S$ -fixed connected geodetic set of $G$ . Hence $S^{'} = V (G) - S$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \geq p - 2$ . Let $S_{1} = {x, y}$ , where $x \in V (K_{m})$ and $y \in V (K_{n})$ , and let $S_{1}^{'} = V (G) - S_{1}$ . It is clear that $S_{1}$ is an independent set of $G$ and $S_{1}^{'}$ is an $S_{1}$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) = p - 2$ .

Based on Theorem 4, we have the following realization result.

Theorem 9. For any three positive integers $a, b$ and $p$ with $2 \leq a \leq b \leq p - 3$ , it is possible to identify a connected graph $G$ of order $p$ with $g_{i f} (G) = a$ and $c g_{i f} (G) = b$ .

Proof. We consider two cases.
Case (1) $2 \leq a = b \leq p - 3$ . Let $P_{p - a - 1} : v_{1}, v_{2}, \dots, v_{p - a - 1}$ be a path of order $p - a - 1$ and let $K_{a + 1}$ be the complete graph of order $a + 1$ . Let $G$ be the graph obtained from $P_{p - a - 1}$ and $K_{a + 1}$ by joining an end vertex $v_{p - a - 1}$ of $P_{p - a - 1}$ with every vertex of $K_{a + 1}$ . The resultant graph $G$ is shown in Figure 4 and its order is $p$ .

It is clear that any independent set of $G$ contains atmost one vertex from the complete graph $K_{a + 1}$ . Also, atleast $a$ vertices in $K_{a + 1}$ lie in every $S$ -fixed geodetic set of $G$ , where $S$ is an independent set of $G$ . Hence $g_{i f} (G) \geq a$ . Let $S = {v_{1}, x}$ and $S^{'} = V (K_{a + 1}) - {x}$ , where $x \in V (K_{a + 1})$ . Since $a \leq p - 3$ , $S$ is an independent set of $G$ and it is clear that every vertex of $V (G) - S$ is on a $v_{1} - y$ geodesic for any $y \in S^{'}$ . Hence $S^{'}$ is an $S$ -fixed geodesic set of $G$ and so $g_{i f} (G) = | S^{'} | = a$ . Also, since $⟨ S^{'} ⟩$ is connected, we have $c g_{i f} (G) = g_{i f} (G) = a$ .
Case (2) $2 \leq a < b \leq p - 3$ . Let $P_{p - a - 2} : v_{1}, v_{2}, \dots, v_{p - b - 2}, \dots, v_{p - a - 2}$ be a path of order $p - a - 2$ . Let $K_{2}$ and $K_{a}$ be two complete graphs of orders $2$ and $a$ , respectively. Let $G$ be the graph obtained from $P_{p - a - 2}$ , $K_{2}$ and $K_{a}$ , by joining the vertex $v_{p - b - 1}$ of $P_{p - a - 2}$ with every vertex of $K_{2}$ and joining the end vertex $v_{p - a - 2}$ of $P_{p - a - 2}$ with every vertex of $K_{a}$ . The resultant graph $G$ is shown in Figure 5 and its order is $p$ .

It is clear that any independent set of $G$ contains atmost one vertex from each complete graphs $K_{2}$ and $K_{a}$ . Also, atleast one vertex in $K_{2}$ and atleast $a - 1$ vertices in $K_{a}$ lie in every $S$ -fixed geodetic set of $G$ , where $S$ is any independent set of $G$ . Hence $g_{i f} (G) \geq a$ . Let $S = {v_{1}, x, y}$ and let $S^{'} = (V (K_{2}) - {x}) \cup (V (K_{a}) - {y})$ , where $x \in V (K_{2})$ and $y \in V (K_{a})$ . Since $a < b \leq p - 3$ , $S$ is an independent set of $G$ and it is clear that every vertex of $V (G) - S$ lies on a $u - v$ geodesic for some $u$ in $S$ and $v$ in $S^{'}$ . Hence $S^{'}$ is an $S$ -fixed geodetic set of $G$ and so $g_{i f} (G) = | S^{'} | = a$ . But $⟨ S^{'} ⟩$ is not connected and so $c g_{i f} (G) > a$ . Since every $S$ -fixed geodetic set of $G$ contains atleast one vertex from each complete graphs $K_{2}$ and $K_{a}$ , every $S$ -fixed connected geodetic set of $G$ contains the cut vertices ${v_{p - b - 1}, v_{p - b}, \dots, v_{p - a - 2}}$ . Let $S^{″} = S^{'} \cup {v_{p - b - 1}, v_{p - b}, \dots, v_{p - a - 2}}$ . It is clear that $S^{″}$ is a minimum $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) = | S^{″} | = b$ .

We know that the diameter of any connected graph lies between its radius and two times of its radius. For that Ostrand [17] has given a realization result. Ostrand’s theorem can be extended so that $c g_{i f} (G)$ can also be prescribed.

Theorem 10. For any three positive integers $r, d$ and $n$ with $r \leq d \leq 2 r$ , a connected graph $G$ can be identified with radius $r$ , diameter $d$ and the independent fixed connected geodetic number $n$ .

Proof. If $r = 1$ , then $d = 1$ or $2$ . If $d = 1$ , then by Theorem 7, $G = K_{n + 1}$ has the desired property. Now, let $d = 2$ . Let $G$ be the graph obtained from the complete graphs $K_{2}$ and $K_{n + 2}$ by merging a vertex of $K_{2}$ , say $y$ , and a vertex of $K_{n + 2}$ . Then $G$ has radius 1, diameter 2 and is shown in Figure 6.

Let $T = V (K_{n + 2}) - {y}$ . If $S$ is any independent set of $G$ , then atleast $n$ vertices in $T$ lie in every $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \geq n$ . Let $S = {x, z}$ , where $z \neq y$ in $K_{n + 2}$ , and let $S^{'} = T - {z}$ . Clearly, $S$ is an independent set of $G$ and $S^{'}$ is the minimum $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) = n$ .

Now, let $r \geq 2$ . We construct a graph $G$ which meets our requirement.
Case (1) $r = d$ . Let $K_{n + 2}$ be the complete graph with vertex set $V (K_{n + 2}) = {u_{1}, u_{2}, \dots, u_{n + 2}}$ and let $C_{2 r}$ be the even cycle with vertex set $V (C_{2 r}) = {v_{1}, v_{2}, \dots, v_{2 r}}$ . Let $G$ be the graph obtained from $K_{n + 2}$ and $C_{2 r}$ by merging the edge $u_{1} u_{2}$ in $K_{n + 2}$ and $v_{r} v_{r + 1}$ in $C_{2 r}$ . The resultant graph $G$ is shown in Figure 7.

It can be easily verified that $e (v) = r$ for any vertex $v \in G$ and so $r a d G = d i a m G = r$ . Also, $T = V (K_{n + 2}) - {u_{1}, u_{2}}$ is the set of all simplicial vertices of $G$ and any independent set of $G$ contains atmost one element in $T$ . If $S$ is any independent set of $G$ , then atleast $n - 1$ vertices in $T$ lie in every $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) \geq n - 1$ . Also, it is clear that all the vertices of $C_{2 r}$ are not on any $x - y$ geodesic for some $x \in V (C_{2 r})$ and $y \in T$ . Hence $c g_{i f} (G) > n - 1$ . Let $S = {v_{1}, u_{3}}$ and let $S^{'} = (T - {u_{3}}) \cup {v_{r + 1}}$ . Clearly, every vertex of $C_{2 r}$ is on a $v_{1} - v_{r + 1}$ geodesic and so $S^{'}$ is an $S$ -fixed geodetic set of $G$ . Also, $⟨ S^{'} ⟩$ is connected and so $c g_{i f} (G) = n$ .
Case (2) $r < d \leq 2 r$ . Let $K_{n + 1}$ be the complete graph with the vertex set $V (K_{n + 1}) = {u_{1}, u_{2}, \dots, u_{n + 1}}$ , let $P_{d - r}$ be a path with the vertex set $V (P_{d - r}) = {v_{1}, v_{2}, \dots, v_{d - r}}$ and let $C_{2 r}$ be the cycle with the vertex set $V (C_{2 r}) = {w_{1}, w_{2}, \dots, w_{2 r}}$ . Let $G$ be the graph obtained from $K_{n + 1}, P_{d - r}$ and $C_{2 r}$ by joining every vertex of $K_{n + 1}$ with the vertex $v_{1}$ in $P_{d - r}$ , and joining the vertex $v_{d - r}$ of $P_{d - r}$ with the vertex $w_{1}$ in $C_{2 r}$ . The graph $G$ is shown in Figure 8.

It can be easily verified that $r \leq e (x) \leq d$ , $e (w_{1}) = r$ and $e (w_{r + 1}) = d$ . Hence $r a d G = r$ and $d i a m G = d$ . It is clear that $T = V (K_{n + 1})$ is the set of all simplicial vertices of $G$ . Then by an argument similar to Case (1) of Theorem 2.10, we have $S = {u_{1}, w_{r + 1}}$ is an independent set of $G$ and $S^{'} = T - {u_{1}}$ is a minimum $S$ -fixed connected geodetic set of $G$ . Hence $c g_{i f} (G) = n$ .

3. Connected Geo-independent Number

Definition 4. The minimum (maximum) independent set required to form a $c g_{i f}$ -set of $G$ is called a connected geo-independent set (upper connected geo-independent set) of $G$ . The cardinality of a connected geo-independent set (upper connected geo-independent set) of $G$ is called the connected geo-independent number (upper connected geo-independent number) of $G$ and is denoted by $c g i n (G)$ ( $c g i n^{+} (G)$ ).

Example 2. For the graph $G$ given in Figure 2.1, we have $c g_{i f} (G) = 3$ . From Table 1, it can be easily seen that $S_{1} = {x_{1}, x_{4}}, S_{2} = {x_{1}, x_{6}}$ , $S_{3} = {x_{2}, x_{4}}$ and $S_{4} = {x_{2}, x_{6}}$ are the connected geo-independent sets of $G$ , $S_{5} = {x_{1}, x_{4}, x_{6}}$ and $S_{6} = {x_{2}, x_{4}, x_{6}}$ are the upper connected geo-independent sets of $G$ . Hence $c g i n (G) = 2$ and $c g i n^{+} (G) = 3$ .

The following result gives the connected geo-independent numbers and the upper connected geo-independent numbers of certain special classes of graphs.

Result 11.

If $G = P_{p}$ , then $c g i n (G) = 1$ and $c g i n^{+} (G) = ⌈ \frac{p}{2} ⌉$ .
If $G = K_{1, p - 1} (p \geq 3)$ , then $c g i n (G) = p - 2$ and $c g i n^{+} (G) = p - 1$ .
If $G = K_{p}$ , then $c g i n (G) = c g i n^{+} (G) = 1$ .
If $G = C_{p}$ , then $c g i n (G) = 1$ and $c g i n^{+} (G) = ⌊ \frac{p}{2} ⌋$ or $⌊ \frac{p}{2} ⌋ - 1$ according as $⌊ \frac{p}{2} ⌋$ is odd or even.
If $G = K_{m, n}$ $(2 \leq m \leq n)$ , then $c g i n (G) = m - 1$ and $c g i n^{+} (G) = n - 1$ .
If $G = Q_{n}$ $(n \geq 3)$ , then $c g i n (G) = 1$ and $c g i n^{+} (G) = 2^{n - 1}$ .

The following observation is an easy consequence of some of the previous results.

Observation 12. For any connected graph $G$ of order $p \geq 2$ ,

$1 \leq c g i n (G) \leq c g i n^{+} (G) \leq β (G) \leq p - 1$ , where $β (G)$ is the independence number of $G$ .
$2 \leq c g i n (G) + c g_{i f} (G) \leq p$ and $2 \leq c g i n^{+} (G) + c g_{i f} (G) \leq p$ .

Theorem 13. Let $G$ be a connected graph of order $p \geq 2$ . Then

$c g i n (G) = 1$ if and only if $c g_{x} (G) = c g_{i f} (G)$ for some vertex $x$ in $G$ .
$c g i n (G) = p - 1$ if and only if $G = K_{2}$ .
$c g i n^{+} (G) = p - 1$ if and only if $G = K_{1, p - 1}$ .

Proof. (i) Let $c g i n (G) = 1$ . Then there exists a vertex, say $x$ , in $G$ with $S = {x}$ and $S^{'}$ , a minimum $S$ -fixed connected geodetic set of $G$ . Hence every vertex of $G$ is on an $x - y$ geodesic for some $y \in S^{'}$ and $⟨ S^{'} ⟩$ is connected, and so $S^{'}$ is a minimum connected $x$ -geodominating set of $G$ . Hence $c g_{x} (G) = | S^{'} | = c g_{i f} (G)$ . Converse is clear from the respective definitions.
(ii) Let $c g i n (G) = p - 1$ . If $p = 2$ , then we get the required result. So, let $p \geq 3$ . Since the connected graph $G$ has $p - 1$ independent vertices, all the independent vertices are end vertices of $G$ . Hence $G$ is a star. Then by Result 11(ii), $c g i n (G) = p - 2$ , but this leads to a contradiction. Conversely, let $G = K_{2}$ . Then by Result 11(iii), $c g i n (G) = 1 = p - 1$ .
(iii) The result follows from the proof of (ii) and Result 1(ii).

Problem 14. Characterize graphs $G$ for which $c g i n^{+} (G) = 1$ .

The following theorem gives a realization result.

Theorem 15. For any four positive integers $a, b, c$ and $n$ with $2 \leq a \leq b \leq c$ , a connected graph $G$ can be identified with $c g i n (G) = a$ , $c g i n^{+} (G) = b$ , $β (G) = c$ and $c g_{i f} (G) = n$ .

Proof. Case (1) $a = b$ . Let $H_{1}, H_{2}, H_{3}$ and $H_{4}$ be the complete graphs with vertex sets $V (H_{1}) = {x, y}, V (H_{2}) = {u_{1}, u_{2}, \dots, u_{c - a + 1}}, V (H_{3}) = {v_{1}, v_{2}, \dots, v_{a - 2}}$ and $V (H_{4}) = {w_{1}, w_{2}, \dots, w_{n + 1}}$ respectively. Let the graph $G$ be constructed using $\bar{H_{1}}, \bar{H_{2}}, \bar{H_{3}}$ and $H_{4}$ by (i) joining the vertices $x$ and $y$ in $\bar{H_{1}}$ with every vertex of $\bar{H_{2}}$ and (ii) joining the vertex $y$ in $\bar{H_{1}}$ with every vertex of $\bar{H_{3}} \cup H_{4}$ . The resultant graph $G$ is shown in Figure 9.

Every independent set of $G$ contains atmost one vertex from $H_{4}$ . Then atleast $n$ vertices in the complete graph $H_{4}$ lie on every $S$ -fixed geodetic set of $G$ , where $S$ is an independent set of $G$ . Hence $c g_{i f} (G) \geq n$ . Let $S = {x, v_{1}, v_{2}, \dots, v_{a - 2}, w_{i}}$ and let $S^{'} = V (H_{4}) - {w_{i}}$ for any $i (1 \leq i \leq n + 1)$ . Clearly $S$ is an independent set of $G$ and every vertex of $V (G) - S$ is on an $x - s$ geodesic for any $s \in S^{'}$ and $⟨ S^{'} ⟩$ is connected. Hence $S^{'}$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) = | S^{'} | = n$ . Also, it is clear that, for any independent set $S$ of $G$ , every minimum $S$ -fixed connected geodetic set contains $n$ vertices from $H_{4}$ .

Let $T$ be any independent set of $G$ with $T^{'}$ , a $T$ -fixed connected geodetic set of $G$ and $| T^{'} | = c g_{i f} (G) = n$ . Hence $T^{'} \subset V (H_{4})$ . Now claim that $V (\bar{H_{3}}) \subseteq T$ . If not, let $z \in V (\bar{H_{3}})$ and $z \notin T$ . Since $z$ is an end vertex of $G$ , $z$ is not an internal vertex of any geodesic and so $z \in T^{'}$ , which is a contradiction to $T^{'} \subset V (H_{4})$ . Hence $V (\bar{H_{3}}) \subseteq T$ . Also, since $c g_{i f} (G) = n$ and $T^{'} \subset V (H_{4})$ , exactly one vertex in $H_{4}$ , say $w_{1}$ , belongs to $T$ . Since $w_{1}$ is adjacent to $y$ , $y \notin T$ . Then either $x$ or $u_{i} (1 \leq i \leq c - a + 1)$ but not both belongs to $T$ .
Subcase (1) $x \in T$ . Then every vertex of $G - \bar{H_{3}}$ is on an $x - w$ geodesic for any $w \in T^{'}$ and so $T = V (\bar{H_{3}}) \cup {x, w_{1}}$ is an independent set of $G$ with $T^{'}$ , a $T$ -fixed connected geodetic set of $G$ and $| T^{'} | = n$ .
Subcase (2) $u_{i} \in T (1 \leq i \leq c - a + 1)$ . If all the vertices $u_{i} \in T$ , then $x$ is not an internal vertex of any $s - t$ geodesic for any $s \in T$ and $t \in T^{'}$ . Hence $x \in T^{'}$ , which is a contradiction to $T^{'} \subset V (H_{4})$ . If atleast one vertex $u_{i} \notin T$ , then $u_{i}$ is not an internal vertex of any $s - t$ geodesic for any $s \in T$ and $t \in T^{'}$ . Hence $u_{i} \in T^{'}$ , which is a contradiction to $T^{'} \subset V (H_{4})$ . Thus $T_{i} = V (\bar{H_{3}}) \cup {x, w_{i}}$ , where $w_{i} \in V (H_{4})$ $(1 \leq i \leq n + 1)$ , is the independent set of $G$ with $T_{i}^{'} = V (H_{4}) - {w_{i}}$ , the $T_{i}$ -fixed connected geodetic set of $G$ and $| T_{i}^{'} | = n$ . Hence $c g i n (G) = c g i n^{+} (G) = a$ .
Claim $β (G) = c$ . It can be easily verified that $W_{i} = V (\bar{H_{2}} \cup \bar{H_{3}}) \cup {w_{i}}$ , where $1 \leq i \leq n + 1$ , is a maximum independent set of $G$ and so $β (G) = c$ .
Case (2) $a < b$ . Let $H_{1}, H_{2}, H_{3}, H_{4}$ and $H_{5}$ be the complete graphs with vertex sets $V (H_{1}) = {x, y, z}, V (H_{2}) = {u_{1}, u_{2}, \dots, u_{c - b + 1}}, V (H_{3}) = {v_{1}, v_{2}, \dots, v_{a - 2}}, V (H_{4}) = {w_{1}, w_{2}, \dots, w_{b - a}}$ and $V (H_{5}) = {t_{1}, t_{2}, \dots, t_{n + 1}}$ , respectively. Let $G$ be the graph obtained from $\bar{H_{1}}, \bar{H_{2}}, \bar{H_{3}}, \bar{H_{4}}$ and $H_{5}$ by (i) joining the vertices $x$ and $y$ in $\bar{H_{1}}$ with every vertex of $\bar{H_{2}}$ , (ii) joining the vertex $y$ in $\bar{H_{1}}$ with every vertex of $\bar{H_{3}}$ , (iii) joining the vertices $y$ and $z$ in $\bar{H_{1}}$ with every vertex of $\bar{H_{4}}$ , and (iv) joining the vertex $z$ in $\bar{H_{1}}$ with every vertex of $H_{5}$ . The resultant graph $G$ is shown in Figure 10.

By an argument similar to Case (1), for any independent set $S$ of $G$ , every minimum $S$ -fixed connected geodetic set contains atleast $n$ vertices from $H_{5}$ . Let $S = V (\bar{H_{3}}) \cup {x, t_{1}}$ and let $S^{'} = V (H_{5}) - {t_{1}}$ . Then clearly $S$ is an independent set of $G$ and $S^{'}$ is an $S$ -fixed connected geodetic set of $G$ and so $c g_{i f} (G) = | S^{'} | = n$ .

Next, prove that $c g i n (G) = a$ . By an argument similar to Case (1), to form an $S$ -fixed connected geodetic set $S^{'}$ with $| S^{'} | = n$ , we need all the vertices in $\bar{H_{3}}$ , the vertex $x$ in $\bar{H_{1}}$ and exactly one vertex in $H_{5}$ for $S$ . Hence $c g i n (G) \geq a$ . As in the above paragraph, $S = V (\bar{H_{3}}) \cup {x, t_{1}}$ is an independent set of $G$ and $S^{'} = V (H_{5}) - {t_{1}}$ is the $S$ -fixed connected geodetic set with $| S^{'} | = n$ . Hence $S$ is a connected geo-independent set of $G$ and so $c g i n (G) = | S | = a$ .

Claim that $c g i n^{+} (G) = b$ . Let $T$ be any independent set of $G$ with $T^{'}$ , a $T$ -fixed connected geodetic set of $G$ and $| T^{'} | = c g_{i f} (G) = n$ . Then by an argument similar to Case (1), $V (\bar{H_{3}}) \cup {x, t_{i}} \subseteq T_{i}, V (H_{5}) - {t_{i}} = T_{i}^{'}$ for any $i$ $(1 \leq i \leq n + 1)$ , and $s \notin T_{i}$ , where $s \in V (\bar{H_{2}}) \cup {y, z}$ . Let $S_{i} = V (\bar{H_{3}} \cup \bar{H_{4}}) \cup {x, t_{i}}$ . Then clearly $S_{i}$ is a maximum independent set of $G$ with $S_{i}^{'} = V (H_{5}) - {t_{i}}$ , the $S_{i}$ -fixed connected geodetic set of $G$ and $| S_{i}^{'} | = n$ . Hence $c g i n^{+} (G) = | S_{i} | = b$ .

It can be easily verified that $W_{i} = V (\bar{H_{2}} \cup \bar{H_{3}} \cup \bar{H_{4}}) \cup {t_{i}}$ , where $1 \leq i \leq n + 1$ , is a maximum independent set of $G$ and so $β (G) = c$ .

Conflict of Interest

The authors declare no conflict of interests.

References:

Buckley, F. and Harary, F., 1990.Distance in Graphs. Addison-Wesley.[Google Scholor]
Chartrand, G.and Zhang, P., 2005. Introduction to Graph Theory. McGraw Hill Education (India) Private Limited.[Google Scholor]
Harary, F., 1969. Graph Theory. Addison-Wesley.
Buckley, F., Harary, F. and Quintas, L. V., 1988. Extremal results on the geodetic number of a graph. Scientia A2, 17(1988), pp.17-26.[Google Scholor]
Kim, B. K., 2004. The geodetic number of a graph. Journal of Computational and Applied Mathematics, 16(1-2), pp.525-532.[Google Scholor]
Chartrand, G., Harary, F., Swart, H.C. and Zhang, P., 2001. Geodomination in graphs. Bulletin of the ICA, 31, pp.51-59.[Google Scholor]
Chartrand, G., Harary, F.and Zhang, P., 2002. On the geodetic number of a graph. Networks, 39, pp.1-6.[Google Scholor]
Harary, F., Loukakis, E.and Tsouros, C., 1993. The geodetic number of a graph. Mathematical and Computer Modelling, 17(11), pp.87-95.[Google Scholor]
Santhakumaran, A. P., Titus, P. and John, J., 2009. On the connected geodetic number of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing, 69, pp.219-229.[Google Scholor]
Santhakumaran, A. P., Titus, P. and John, J., 2009. The upper connected geodetic number and forcing connected geodetic number of a graph. Discrete Applied Mathematics, 157, pp.1571-1580.[Google Scholor]
Santhakumaran, A. P.and Titus, P., 2005. Vertex geodomination in graphs. Bulletin of Kerala Mathematics Association, 2(2), pp.45-57.
Santhakumaran, A. P. and Titus, P., 2011. On the vertex geodomination number of a graph. Ars Combinatoria, 101, pp.137-151.[Google Scholor]
Santhakumaran, A. P. and Titus, P., 2012. The geo-number of a graph. Ars Combinatoria, 106, pp.65-78.[Google Scholor]
Santhakumaran, A. P. and Titus, P., 2009. The connected vertex geodomination number of a graph. Journal of Prime Research in Mathematics, 5, pp.101-114.[Google Scholor]
Santhakumaran, A. P. and Titus, P., 2009. The edge fixed geodomination number of a graph. Analele Stiintifice ale Universitatii Ovidius Constanta, 17(1), pp.187-200.[Google Scholor]
Titus, P.and Antin Mary, S., Communicated. Computation of independent fixed geodetic number of a graph.
Ostrand, P. A., 1973. Graphs with specified radius and diameter. Discrete Mathematics, 4, pp.71-75.[Google Scholor]

[1] Buckley, F. and Harary, F., 1990.Distance in Graphs. Addison-Wesley.[Google Scholor]

[2] Chartrand, G.and Zhang, P., 2005. Introduction to Graph Theory. McGraw Hill Education (India) Private Limited.[Google Scholor]

[3] Harary, F., 1969. Graph Theory. Addison-Wesley.

[4] Buckley, F., Harary, F. and Quintas, L. V., 1988. Extremal results on the geodetic number of a graph. Scientia A2, 17(1988), pp.17-26.[Google Scholor]

[5] Kim, B. K., 2004. The geodetic number of a graph. Journal of Computational and Applied Mathematics, 16(1-2), pp.525-532.[Google Scholor]

[6] Chartrand, G., Harary, F., Swart, H.C. and Zhang, P., 2001. Geodomination in graphs. Bulletin of the ICA, 31, pp.51-59.[Google Scholor]

[7] Chartrand, G., Harary, F.and Zhang, P., 2002. On the geodetic number of a graph. Networks, 39, pp.1-6.[Google Scholor]

[8] Harary, F., Loukakis, E.and Tsouros, C., 1993. The geodetic number of a graph. Mathematical and Computer Modelling, 17(11), pp.87-95.[Google Scholor]

[9] Santhakumaran, A. P., Titus, P. and John, J., 2009. On the connected geodetic number of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing, 69, pp.219-229.[Google Scholor]

[10] Santhakumaran, A. P., Titus, P. and John, J., 2009. The upper connected geodetic number and forcing connected geodetic number of a graph. Discrete Applied Mathematics, 157, pp.1571-1580.[Google Scholor]

[11] Santhakumaran, A. P.and Titus, P., 2005. Vertex geodomination in graphs. Bulletin of Kerala Mathematics Association, 2(2), pp.45-57.

[12] Santhakumaran, A. P. and Titus, P., 2011. On the vertex geodomination number of a graph. Ars Combinatoria, 101, pp.137-151.[Google Scholor]

[13] Santhakumaran, A. P. and Titus, P., 2012. The geo-number of a graph. Ars Combinatoria, 106, pp.65-78.[Google Scholor]

[14] Santhakumaran, A. P. and Titus, P., 2009. The connected vertex geodomination number of a graph. Journal of Prime Research in Mathematics, 5, pp.101-114.[Google Scholor]

[15] Santhakumaran, A. P. and Titus, P., 2009. The edge fixed geodomination number of a graph. Analele Stiintifice ale Universitatii Ovidius Constanta, 17(1), pp.187-200.[Google Scholor]

[16] Titus, P.and Antin Mary, S., Communicated. Computation of independent fixed geodetic number of a graph.

[17] Ostrand, P. A., 1973. Graphs with specified radius and diameter. Discrete Mathematics, 4, pp.71-75.[Google Scholor]

Contents

Ars Combinatoria

Independent Fixed Connected Geodetic Number of a Graph

Abstract

1. Introduction

2. Independent fixed connected geodetic number

3. Connected Geo-independent Number

Conflict of Interest

References:

Information

Guidelines

CP Initiatives

Follow CP