Ratio Mathematica                                                                            Volume 45, 2023 

` 

 

 
  

 

The Connected Vertex Strong Geodetic 

Number of a Graph 
 

 

C. Saritha* 

T. Muthu Nesa Beula† 

 
 

Abstract 

In this paper we introduce the concept of connected vertex strong geodetic 

number 𝑐𝑔𝑠𝑥 (𝐺) of a graph 𝐺 at a vertex 𝑥 and investigate its properties. We 
determinebounds for it and find the same for some special classes of graphs. We prove 

that𝑠𝑔𝑥 (𝐺) ≤ 𝑐𝑠𝑔𝑥 (𝐺) for any vertex 𝑥 in 𝐺is connected graphs of order 𝑛 ≥  2with 
one are characterized for some vertex 𝑥 in 𝐺.Necessary conditions for𝑠𝑔𝑥 (𝐺) to be 𝑛 or 
𝑛 − 1 are given for some vertex 𝑥 in 𝐺. It is shown for every pair of integers𝑎 and 𝑏 
with 2 ≤  𝑎 ≤ 𝑏, there exists a connected graph 𝐺 such that 𝑠𝑔𝑥 (𝐺) = 𝑎 and 
𝑐𝑠𝑔𝑥 (𝐺) = 𝑏 for some vertex 𝑥 in 𝐺. 

 

Keywords: strong geodetic number;vertex strong geodetic number; connected strong 

geodetic number. 

2010 AMS subject classification: 05C15‡. 

 

 

 

 

 

 

 

 
*Register Number 20123182092003, Research Scholar, Department of Mathematics, Women’s Christian 

College, Nagercoil629 001, Affiliated to Manonmaniam Sundaranar University, Abishekapatti, 

Tirunelveli-627 012, Tamil Nadu, India. saritha.c2012@gmail.com.  
†Assistant Professor, Department of Mathematics, Women’s Christian College, Nagercoil - 629 001, 

Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli-627 012, Tamil Nadu, 

India.tmnbeula@gmail.com. 
‡Received on July 28, 2022. Accepted on October 15, 2022. Published on January 25, 2023. doi: 

10.23755/rm.v45i0.978. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published 

under the CC-BY license agreement. 

52

mailto:saritha.c2012@gmail.com


C. Saritha and T. Muthu Nesa Beula 

 

 

1. Introduction 

By a graph 𝐺 =  (𝑉, 𝐸), we mean a finite, undirected connected graph without loops 
or multiple edges. The order and size of 𝐺 are denoted by 𝑛 and 𝑚 respectively. For 
basic graph theoretic terminology, we refer to [1]. Two vertices 𝑢 and 𝑣 are said to be 
adjacent if 𝑢𝑣 is an edge of 𝐺. Two edges of 𝐺 are said to be adjacent if they have a 
common vertex.  The distance𝑑(𝑢, 𝑣) between two vertices 𝑢 and v in a connected 
graph 𝐺 is the length of a shortest 𝑢-𝑣 path in 𝐺. 

An 𝑢−𝑣 path of length 𝑑(𝑢, 𝑣) is called an 𝑢−𝑣geodesic.An 𝑥 − 𝑦 path of length 
𝑑(𝑥, 𝑦) is called geodesic. A vertex 𝑣 is said to lie on a geodesic 𝑃 if 𝑣 is an internal 
vertex of 𝑃. The closed interval 𝐼[𝑥, 𝑦] consists of 𝑥, 𝑦 and all vertices lying on some 
𝑥 − 𝑦 geodesic of 𝐺 and for a non-empty set 𝑆 ⊆  𝑉 (𝐺), 𝐼[𝑆]  = ∪𝑥,𝑦∈𝑆 𝐼[𝑥, 𝑦]. A set 

𝑆 ⊆  𝑉 (𝐺) in a connected graph 𝐺 is a geodetic set of 𝐺 if 𝐼[𝑆]  =  𝑉 (𝐺). The geodetic 
number of 𝐺, denoted by 𝑔(𝐺), is the minimum cardinality of a geodetic set of 𝐺.The 
geodetic concept were studied in [1, 3, 4]. Let 𝑥 be a vertex of 𝐺 and 𝑆 ⊆ 𝑉 − {𝑥}. Then 
for each vertex𝑦 ∈ 𝑆, 𝑥 ≠ 𝑦. Let �̃�𝑥 [𝑦] be a selected fixed shortest 𝑥-𝑦 path. Then we 
set 𝐼𝑥 [𝑆] = {�̃�𝑥 (𝑦): 𝑦 ∈ 𝑆} and let 𝑉(𝐼𝑥 [𝑆]) = ⋃ 𝑉(𝑃)

𝑝∈𝐼𝑥[𝑆]
. If 𝑉(𝐼𝑥 [𝑆]) = 𝑉 for some 

𝐼𝑥 [𝑆]then the set 𝑆 is called a vertex strong geodetic set of 𝐺. The minimum cardinality 
of a vertex strong geodetic set of 𝐺 is called the vertex strong geodetic number of 𝐺 and 
is denoted by 𝑠𝑔𝑥 (𝐺).The following theorem is used in sequel. 
 

Theorem 1.1[4] Each extreme vertex of a connected graph belong to every geodetic set 

of 𝐺. 

 

2. The connected vertex strong geodetic number of a 

graph 
Definition 2.1. Let 𝑥 be a vertex of 𝐺 and 𝑆 ⊆ 𝑉 − {𝑥}. Then for each vertex𝑦 ∈ 𝑆, 𝑥 ≠
𝑦. Let �̃�𝑥 [𝑦] be a selected fixed shortest 𝑥-𝑦 path. Then we set 𝐼𝑥 [𝑆] = {�̃�𝑥 (𝑦): 𝑦 ∈ 𝑆} 
and let 𝑉(𝐼𝑥 [𝑆]) = ⋃ 𝑉(𝑃)

𝑝∈𝐼𝑥[𝑆]
. If 𝑉(𝐼𝑥 [𝑆]) = 𝑉 for some 𝐼𝑥 [𝑆]then the set 𝑆 is called a 

vertex strong geodetic set of 𝐺. A vertex strong geodetic set S of x of G is called a 
connected vertex strong geodetic set of G if G[S] is connected. The minimum 

cardinality of a connected vertex strong geodetic set of 𝐺 is called the connected vertex 
strong geodetic number of 𝐺 and is denoted by 𝑐𝑠𝑔𝑥 (𝐺). 
 

Example 2.2.For the graph 𝐺 given in Figure 2.1,𝑐𝑠𝑔𝑥-sets and 𝑐𝑠𝑔𝑥 (𝐺) for each 
vertex 𝑥  is given in the following Table 2.1. 

53



The Connected Vertex Strong Geodetic Number of a Graph 

 

 

 

 
 

 

 

Table 2.1 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Observation 2.3. Let 𝑥 be any vertex of a connected graph𝐺. 
(i) If 𝑦 ≠ 𝑥 be a simplicial vertex of 𝐺, then 𝑦 belongs to every connected 𝑥-

vertex strong geodetic set of 𝐺. 
(ii) The eccentric vertices of 𝑥 belong to every connected 𝑥-vertex strong 

geodetic set of 𝐺. 
       In the following we determine the connected vertex strong geodetic number 

of some standard graphs 𝐺 for each vertex in 𝐺. 
Theorem 2.4.For the path𝐺 = 𝑃𝑛 (𝑛 ≥  3),  

𝑐𝑠𝑔𝑥 (𝐺) = {
1 𝑖𝑓 𝑥 𝑖𝑠 𝑎𝑛 𝑒𝑛𝑑 𝑣𝑒𝑟𝑡𝑒𝑥 𝑜𝑓 𝐺 
𝑛  𝑖𝑓 𝑥 𝑖𝑠 𝑎 𝑐𝑢𝑡 𝑣𝑒𝑟𝑡𝑒𝑥 𝑜𝑓 𝐺

 

Proof. Let  𝑃𝑛 be 𝑣1, 𝑣2, … , 𝑣𝑛. 

If 𝑥 = 𝑣1, then 𝑆 = {𝑣𝑛 } is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 1.  Similarly if 
𝑥 = 𝑣𝑛, then 𝑐𝑠𝑔𝑥 (𝐺) = 1. Let 𝑥 be a cut vertex of 𝐺.  Then by Observation 2.3 (i) 

Vertex 𝑐𝑠𝑔𝑥-sets 𝑐𝑠𝑔𝑥 (𝐺) 

𝑣1 {𝑣3, 𝑣4}, {𝑣4, 𝑣5} 2 

𝑣2 {𝑣4, 𝑣5, 𝑣6} 3 

𝑣3 {𝑣1, 𝑣6}, {𝑣5, 𝑣6} 2 

𝑣4 {𝑣1, 𝑣6}, {𝑣1, 𝑣2} 2 

𝑣5 {𝑣1, 𝑣2, 𝑣3} 3 

𝑣6 {𝑣3, 𝑣4}, {𝑣2, 𝑣3} 2 

𝑣1 

𝑣4 𝑣5 𝐺  

Figure 2.1 

 

𝑣2 𝑣3 

𝑣6 

54



C. Saritha and T. Muthu Nesa Beula 

 

{𝑣1, 𝑣𝑛 } is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺.  Let 𝑆 be a 𝑐𝑠𝑔𝑥-set of 𝐺. Since 𝐺[𝑆] is 
connected, it follows that 𝑆 = 𝑉(𝐺) is the unique 𝑐𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛.∎ 

Theorem 2.5.For the cycle 𝐺 = 𝐶𝑛(𝑛 ≥  4), 𝑐𝑠𝑔𝑥 (𝐺) = 2, for every 𝑥 ∈ 𝐺. 
Proof. Let  𝑉(𝐶𝑛) =  {𝑣1, 𝑣2, … , 𝑣𝑛}. Without loss of generality let us assume 

that 𝑥 = 𝑣1. 
Case (i) Let 𝑛 be even. Let 𝑛 = 2𝑘 (𝑘 ≥ 2). Then 𝑣𝑘+1 is the eccentric vertex of 

𝐺. By Observation 2.3(ii) since {𝑣𝑘+1} is not a 𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) ≥ 2.  Let 
𝑆 = {𝑣𝑘+1, 𝑣𝑘+2}.  Then 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 2. 

Case (ii) Let 𝑛 be odd. Let 𝑛 = 2𝑘 + 1 (𝑘 ≥ 2). Then 𝑆 = {𝑣𝑘+1,𝑣𝑘+2} is the 
eccentric vertices of 𝐺.  By Observation 2.3 (ii) 𝑆 is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺 and 
so 𝑐𝑠𝑔𝑥 (𝐺) ≥ 2. Since 𝑆 is a 𝑠𝑔𝑥-set of 𝐺 and 𝐺[𝑆] is connected, 𝑆 is a  𝑐𝑠𝑔𝑥-set of 𝐺 
sothat 𝑐𝑠𝑔𝑥 (𝐺) = 2.∎ 

 
Theorem 2.6.For the complete graph  𝐺 = 𝐾𝑛(𝑛 ≥  4), 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 1, for 

every 𝑥 ∈   𝐺. 
Proof. Let 𝑥 be a vertex of 𝐺. Let 𝑆 = 𝑉(𝐺) − {𝑥}. Since every vertex of 𝐺 is an 

extreme vertex of 𝐺, it follows from Observation 2.3(i), 𝑆 is the unique 𝑐𝑠𝑔𝑥-set of 𝐺 so 
that𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 1 for every vertex 𝑥 in 𝐺.∎ 

 

Theorem 2.7.For the fan graph  𝐺 = 𝐾1 + 𝑃𝑛−1(𝑛 ≥  5). 

𝑐𝑠𝑔𝑥 (𝐺) = {

𝑛 − 1       𝑖𝑓 𝑥 ∈ 𝑉(𝐾1)                           
𝑛 − 3       𝑖𝑓 𝑥 𝑖𝑠 𝑒𝑥𝑡𝑟𝑒𝑚𝑒 𝑣𝑒𝑟𝑡𝑒𝑥 𝑜𝑓 𝑃𝑛−1
𝑛 − 2    𝑖𝑓 𝑥 𝑖𝑠 𝑖𝑛𝑡𝑒𝑟𝑛𝑎𝑙 𝑣𝑒𝑟𝑡𝑒𝑥 𝑜𝑓 𝑃𝑛−1

 

Proof. Let  𝑉(𝐾1) = 𝑦 and 𝑉(𝑃𝑛−1) = {𝑣1, 𝑣2, … , 𝑣𝑛−1}. 
Case (i) Let𝑥 = 𝑦, Then 𝑆 = {𝑣1, 𝑣2, … , 𝑣𝑛 } is a set of all eccentric vertices for 

𝑥. By Observation 2.3 (ii) 𝑆 is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺 and so  𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 1. 
Since 𝐺[𝑆] is connected, 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that  𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 1.  Let 𝑥 ∈
𝑉(𝑃𝑛−1). Let 𝑥 = 𝑣1.  Then 𝑆 = {𝑣3, 𝑣4, … , 𝑣𝑛−1}  are eccentric vertices of 𝐺. By 
Observation 2.3 (ii) 𝑆 is a subset of every 𝑐𝑠𝑔𝑥 -set of 𝐺 and so  𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 3.  Now 
𝑆 is a 𝑠𝑔𝑥-set of 𝐺 and 𝐺[𝑆] is connected.  Therefore 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that 
𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 3.  If 𝑥 = 𝑣𝑛−1, by the similar way we can prove that 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 3. 
Let  𝑥 ∈ {𝑣2, 𝑣3, … , 𝑣𝑛−2}. Without loss of generality let us assume that 𝑥 = 𝑣2. Then 
{𝑣1, 𝑣𝑛−1} is set of extreme vertices of   𝐺.  By Observation 2.3 (i) {𝑣1, 𝑣𝑛−1} is a subset 
of every 𝑐𝑠𝑔𝑥-set of 𝐺. {𝑣4, 𝑣5, … , 𝑣𝑛−2} is the set of eccentric vertices of 𝑣2. Then  
{𝑣4, 𝑣5, … , 𝑣𝑛−2}is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺.  Let 𝑆

′ = {𝑣1, 𝑣4, 𝑣5, … , 𝑣𝑛−2,𝑣𝑛−1,}.  

Then 𝑆′ is a 𝑠𝑔𝑥-set of 𝐺 but 𝐺[𝑆
′] is not connected. Therefore 𝑆′ ∪ {𝑦} is a 𝑐𝑠𝑔𝑥-set of 

𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 2.∎ 
Theorem 2.8.For the wheel graph  𝐺 = 𝐾1 + 𝐶𝑛−1(𝑛 ≥  5). 

𝑐𝑠𝑔𝑥 (𝐺) = {
𝑛 − 1      𝑖𝑓 𝑥 ∈ 𝑣1

𝑛 − 3  𝑖𝑓 𝑥 ∈ 𝑉(𝐶𝑛−1) 
 

Proof. Let  𝑉(𝐾1) = 𝑦  and  𝑉(𝐶𝑛−1) = {𝑣1, 𝑣2, … , 𝑣𝑛−1}. 

55



The Connected Vertex Strong Geodetic Number of a Graph 

 

 

 

Case(i) Let𝑥 = 𝑦, Then 𝑆 = {𝑣1, 𝑣2, … , 𝑣𝑛−1} is a set of all eccentric vertices for 
𝑥. By Observation 2.3 (ii) 𝑆 is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺 and so 𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 1. 
Since 𝐺[𝑆] is connected, 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that  𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 1. 

Case (ii) Let 𝑥 ∈ 𝑉(𝐶𝑛−1). Without loss of generality, let us assume that 𝑥 =
𝑣1. Then 𝑆 = {𝑣3, 𝑣4, … , 𝑣𝑛−1} are eccentric vertices of 𝐺. By Observation 2.3 (ii) 𝑆 is a 
subset of every 𝑐𝑠𝑔𝑥 -set of 𝐺 and so  𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 3.  Now 𝑆 is a 𝑠𝑔𝑥-set of 𝐺 and 
𝐺[𝑆] is connected.  Therefore 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 3.∎ 

Theorem 2.9.For the star graph  𝐺 = 𝐾1,𝑛−1(𝑛 ≥  3), 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 1 for 
every 𝑥 ∈ 𝐺. 

Proof. Let𝑦 be the cut vertex of 𝐺 and {𝑣1, 𝑣2, … , 𝑣𝑛−1} is a set of all eccentric 
vertices of  𝐺.Let𝑥 = 𝑦, Then 𝑆 = {𝑣1, 𝑣2, … , 𝑣𝑛−1} is a set of all eccentric vertices for 
𝑥. By Observation 2.3 (ii) 𝑆 is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺 and so  𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 1. 
Since 𝐺[𝑆] is connected, 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that  𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 1.  Let 𝑥 ∈
{𝑣1, 𝑣2, … , 𝑣𝑛−1} Without loss of generality, let us assume that 𝑥 = 𝑣1. Then 𝑆 =
{𝑣2, 𝑣3, … , 𝑣𝑛−1} are set of eccentric vertices of 𝑣1. By Observation 2.3 (ii) 𝑆 is a subset 
of every 𝑠𝑔𝑥-set of 𝐺 and so  𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 2.  Now 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 but 𝐺[𝑆] is 
not a 𝑐𝑠𝑔𝑥-set of 𝐺 and so 𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 1.  Let 𝑆

′ = 𝑆 ∪ {𝑥}.  Then 𝑆′ is a 𝑐𝑠𝑔𝑥-set 
of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 1.∎ 

 

Theorem 2.10.For the Peterson graph 𝐺, 𝑐𝑠𝑔𝑥 (𝐺) = 6 for every 𝑥 ∈ 𝐺. 

Proof.  

Case (i) Let𝑥 ∈ {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5}.  Without loss of generality let us assume that 

𝑥 = 𝑣1. Then  𝑆 = {𝑣2, 𝑣5, 𝑣7, 𝑣8, 𝑣9, 𝑣10} is the set of all eccentric vertices for 𝑥. By 

Observation 2.3 (ii) 𝑆 is a subset of every 𝑐𝑠𝑔𝑥 -set of 𝐺 and so 𝑐𝑠𝑔𝑥 (𝐺) ≥ 6. Since 𝑆 is 

a 𝑠𝑔𝑥-set of 𝐺 and  𝐺[𝑆] is connected, 𝑆 is a  𝑐𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 6. 

Case (ii) Let𝑥 ∈ {𝑣6, 𝑣7, 𝑣8, 𝑣9, 𝑣10}. Without loss of generality let us assume 

that 𝑥 = 𝑣6. Then 𝑆 = {𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣8, 𝑣9} is the set of all eccentric vertices for 𝑥. By 

Observation 2.3 (ii) 𝑆 is a subset of every 𝑐𝑠𝑔𝑥 -set of 𝐺 and so 𝑐𝑠𝑔𝑥 (𝐺) ≥ 6. Since 𝑆 is 

a 𝑠𝑔𝑥-set of 𝐺 and  𝐺[𝑆] is connected, 𝑆 is a  𝑐𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 6.∎ 

56



C. Saritha and T. Muthu Nesa Beula 

 

 

Theorem 2.11.Let 𝐺 be a connected graph. Then 1 ≤ 𝑠𝑔𝑥 (𝐺) ≤ 𝑐𝑠𝑔𝑥 (𝐺) ≤ 𝑛 
for every    

vertex 𝑥 in 𝐺. 
Proof. Let 𝑥 be a vertex of 𝐺. Since every 𝑠𝑔𝑥-set of 𝐺 needs at least one vertex 

𝑠𝑔𝑥 (𝐺) ≥ 1. Since every connected strong vertex geodetic set of 𝐺 is a strong vertex 
geodetic set of 𝐺, 𝑠𝑔𝑥 (𝐺) ≤ 𝑐𝑠𝑔𝑥 (𝐺). Since 𝑉(𝐺) is a connected strong vertex geodetic 
set of 𝐺, 𝑐𝑠𝑔𝑥 (𝐺) ≤ 𝑛. Therefore 1 ≤ 𝑠𝑔𝑥 (𝐺) ≤ 𝑐𝑠𝑔𝑥 (𝐺) ≤ 𝑛.∎ 

 

Theorem 2.12.Let 𝐺 be a connected graph. Then 𝑐𝑠𝑔𝑥 (𝐺) = 1 if and only if 𝑥 is 
an end   

 vertex of 𝑃𝑛(𝑛 ≥ 2). 
Proof. Let 𝑥 be an end vertex of 𝑃𝑛. Then by Theorem 2.4, 𝑐𝑠𝑔𝑥 (𝐺) = 1. 

Conversely let 𝑐𝑠𝑔𝑥 (𝐺) = 1. Let 𝑆 = {𝑦} be the 𝑐𝑠𝑔𝑥-set of 𝑥. We prove that 𝑥 is an 
end vertex of 𝑃𝑛. On the contrary suppose that 𝑥 is not an end vertex of 𝑃𝑛.  Then there 
are at least two 𝑥 − 𝑦 geodesics, which is a contradiction to 𝑆 a 𝑐𝑠𝑔𝑥-set of 𝐺. 
Therefore 𝑥 is an end vertex of 𝑃𝑛.∎ 

 

Theorem 2.13.Let 𝐺 be a connected graph and 𝑥 ∈ 𝐺. If 𝑥 is a universal vertex 
of 𝐺. Then 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 − 1. 

Proof. Let 𝑥 be a universal vertex of 𝐺. Then 𝑉(𝐺) − {𝑥} is set of all eccentric 
vertices for 𝑥. By Observation 2.3 (ii), 𝑆 is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺 and so 
𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 1. Since 𝐺[𝑆] is connected, 𝑆 is a 𝑐𝑠𝑔𝑥-set of 𝐺 so that 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛 −
1.∎ 

Theorem 2.14.Let 𝐺 be a connected graph and 𝑥 ∈ 𝐺. If 𝑥 is a cut vertex and 
universal vertex of 𝐺. Then𝑐𝑠𝑔𝑥 (𝐺) = 𝑛. 

Proof. Since 𝑥 is a universal vertex of 𝐺, then 𝑉(𝐺) − {𝑥} is set of all eccentric 
vertices for 𝑥. By Observation 2.3 (ii), 𝑆 is a subset of every 𝑐𝑠𝑔𝑥-set of 𝐺 and so 

𝑣9 

𝑣10 

G 

Figure 2.2 

 

𝑣4 

𝑣2 

𝑣6 

𝑣8 

𝑣3 

𝑣5 

𝑣1 
𝑣7 

57



The Connected Vertex Strong Geodetic Number of a Graph 

 

 

 

𝑐𝑠𝑔𝑥 (𝐺) ≥ 𝑛 − 1. Since 𝐺[𝑆] is not connected, 𝑆 is not a 𝑐𝑠𝑔𝑥-set of 𝐺. Therefore 𝑆 =
𝑉(𝐺) is the unique  𝑐𝑠𝑔𝑥-set of 𝐺. Hence 𝑐𝑠𝑔𝑥 (𝐺) = 𝑛.∎ 

Theorem 2.15. For every pair of integers𝑎 and 𝑏 with 2 ≤  𝑎 ≤ 𝑏, there exists a 
connected graph 𝐺 such that 𝑠𝑔𝑥 (𝐺) = 𝑎 and 𝑐𝑠𝑔𝑥 (𝐺) = 𝑏 for some vertex 𝑥 in 𝐺. 

Proof.For 𝑎 = 𝑏, let 𝐺 = 𝐾𝑎+1. Then by Theorem 2.11𝑠𝑔𝑥 (𝐺) = 𝑐𝑠𝑔𝑥 (𝐺) = 𝑎 
for every vertex 𝑥 in 𝐺. For 𝑏 = 𝑎 + 1,let 𝐺 = 𝐾1,𝑎. Let 𝑥 be a universal vertex of 𝐺. 
Then by Theorem 2.14,𝑠𝑔𝑥 (𝐺) = 𝑎 and 𝑐𝑠𝑔𝑥 (𝐺) = 𝑎 + 1.  So, let 𝑏 ≥ 𝑎 + 2. Let 
𝑃0: 𝑢0, 𝑢1,  𝑢2, … , 𝑢𝑏−𝑎, 𝑢𝑏−𝑎+1be a path of order 𝑏 − 𝑎 + 2. Let 𝐺 be the graph 
obtained from 𝑃 by adding the new vertices  𝑧1, 𝑧2, … , 𝑧𝑎−1 and introducing 
the edges 𝑧𝑖 𝑢 (1 ≤  𝑖 ≤  𝑏 − 𝑎 + 1). The graph 𝐺is shown in Figure 2.3. Let 𝑥 =
𝑢𝑏−𝑎+1. 

 First we prove that  𝑠𝑔𝑥(𝐺) = 𝑎.Let𝑆 = {𝑢0, 𝑧1, 𝑧2, … , 𝑧𝑎−1, 𝑢𝑏−𝑎+1}be 
the end vertices of 𝐺. By Observation 2.3(i), 𝑆1 = 𝑆 − {𝑢𝑏−𝑎+1} is a subset of 
every 𝑠𝑔𝑥-set of 𝐺 and so 𝑠𝑔𝑥 (𝐺) ≥ 𝑎. Since 𝑆1 is a 𝑠𝑔𝑥-set of 𝐺, 𝑠𝑔𝑥 (𝐺) = 𝑎. 

Next we prove that 𝑐𝑠𝑔𝑥 (𝐺)= 𝑏.By Observation, 𝑆1 is a subset of every𝑐𝑠𝑔𝑥-set 
of 𝐺. Since 𝐺[𝑆1] is not connected 𝑆1 is not a 𝑐𝑠𝑔𝑥-set of 𝐺. let 𝑆2 = 𝑆1 ∪
{𝑢1, 𝑢2, … , 𝑢𝑏−𝑎}.  Then 𝑆2 is a 𝑐𝑠𝑔𝑥-set of 𝐺 and𝐺[𝑆2] is connected. Therefore 𝑆2 is 
a 𝑐𝑠𝑔𝑥-set of 𝐺 so that , 𝑐𝑠𝑔𝑥 (𝐺) = 𝑏.∎ 

 

 

 

3. Conclusions 

In this article we explore the concept of the forcing strong geodetic number of a graph. 

We extend this concept to some other distance related parameters in graphs. 

 

 

 

 

 

 

  

 

 

𝑧1 

 

 

𝑧2 
𝑧𝑎−1 

𝑢2 𝑢𝑏−𝑎 

        𝐺 
Figure 2.3 

𝑢0 𝑢1 𝑢𝑏−𝑎+1 

58



C. Saritha and T. Muthu Nesa Beula 

 

References 

[1] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood City, 

CA, 1990. 

[2] L. G. Bino Infanta and D. Antony Xavier, Strong upper geodetic number of graphs, 

Communications in Mathematics and Applications 12(3), (2021)737–748. 

[3]G. Chartrand and P. Zhang, The forcing geodetic number of a graph, Discuss. Math. 

Graph Theory, 19 (1999), 45-58. 

[4]G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks, 

39(2002), 1-6. 

[5] V. Gledel, V. Irsic, and S. Klavzar, Strong geodetic cores and Cartesian product 

graphs, arXiv: 1803. 11423 [math.CO] (30 Mar 2018). 

[6]Huifen Ge, Zao Wang-and Jinyu Zou Strong geodetic number in some networks, 

Journal of Mathematical Resarch-11(2), (2019), 20-29. 

[7] V. Irsic, Strong geodetic number of complete bipartite graphs and of graphs with 

specified diameter, Graphs and Combin. 34 (2018) 443–456. 

[8] V. Irsic, and S. Klavzar, Strong geodetic problem on Cartesian products of graphs, 

RAIRO Oper. Res. 52 (2018) 205–216. 

[9] P. Manuel, S. Klavzar, A. Xavier, A. Arokiaraj, and E. Thomas, Strong edge 

geodetic problem in networks, Open Math. 15 (2017) 1225–1235. 

[10] C. Saritha and T. Muthu Nesa Beula, The forcing strong geodetic number of a 

graph,        proceedings of the International conference on Advances and Applications in 

Mathematical Sciences, 2022, 76-80. 

[11] C. Saritha and T. Muthu Nesa Beula, The vertex strong geodetic number of a 

graph, (Communicated).   

 

 

 

59