Ratio Mathematica Volume 45, 2023 Forcing vertex square free detour number of a graph G. Priscilla Pacifica ∗ K. Christy Rani† Abstract Let G be a connected graph and S a square free detour basis of G. A subset T ⊆ S is called a forcing subset for S if S is the unique square free detour basis of S containing T . A forcing subset for S of minimum order is a minimum forcing subset of G. The forcing square free detour number of G is fdn �fu (G) = min{fdn �fu (Su)}, where the minimum is taken over all square free detour bases S in G. In this paper, we introduce the forcing vertex square free detour sets. The general properties satisfied by these forcing subsets are discussed and the forcing square free detour number for a certain class of standard graphs are determined. We show that the two parameters dn �fu (G) and fdn �fu (G) satisfy the relationship 0 ≤ fdn �fu (G) ≤ dn �fu (G). Also, we prove the existence of a graph G with fdn �fu (G) = α and dn �fu (G) = β, where 0 ≤ α ≤ β and β ≥ 2 for some vertex u in G. Keywords: forcing square free detour number; forcing vertex square free detour set; forcing vertex square free detour number. 2020 AMS subject classifications: 05C12, 05C691 ∗Assistant Professor, Department of mathematics, St. Mary’s College(Autonomous), Thoothukudi - 628 001; priscillamelwyn@gmail.com; e-mail@address. †Research Scholar, Reg. No.: 20122212092002, Department of Mathematics, St. Mary’s Col- lege(Autonomous), Thoothukudi - 628 001, Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli - 627 012, Tamilnadu, India ; christy.agnes@gmail.com 1Received on June 5, 2022. Accepted on August 25, 2022. Published on January 30, 2023. DOI: 10.23755/rm.v45i0.1030. ISSN: 1592-7415. eISSN: 2282-8214. c©The Authors. This paper is published under the CC-BY licence agreement. 286 G. Priscilla Pacifica and K. Christy Rani 1 Introduction In a simple connected graph G = (V,E) of order at least two, a longest xy path is called an x− y detour path for any two vertices x and y in G. A set S of vertices of G is a detour set of G if each vertex v of G lies on an x − y detour path for some elements x and y in S. The minimum cardinality of a detour set of G is the detour number of G and is denoted by dn(G). A subset T of a minimum detour set S of G is a forcing detour subset for S if S is the unique detour basis containing T . A forcing detour subset for S of minimum cardinality is a mini- mum forcing detour subset of S. The forcing detour number fdn(S) of S, is the minimum cardinality of a forcing detour subset for S. The forcing detour num- ber fdn(G) of G, is min{fdn(S)}, where the minimum is taken over all detour bases S in G. This notion of forcing detour number was initiated by Chartrand et al. [2003]. From then onwards there have been many relevant studies about the forcing detour concept in the past few decades. The connected detour parameter was defined by Santhakumaran and Athisayanathan [2009]. Also, Santhakumaran and Athisayanathan [2010] focussed on edge of a graph and introduced forcing edge detour number and the forcing weak edge detour number. Further results on connected detour number was studied by Ali and Ali [2019]. Titus and Balakr- ishnan [2016] concentrated on a vertex of a graph and compiled the findings on forcing vertex detour monophonic number arising from the chordless path. Rama- lingam et al. [2016] extended this concept to triangle free and extracted forcing re- sults. The square free detour concept was introduced by Rani and Pacifica [2022]. Though there are several novel forcing parameters, this paper aims at filling some significant research gaps and brings forth the results on the forcing vertex square free detour number of a graph. We determine the bounds for it and compare the relationship with the vertex square free detour number of a graph. These ideas have interesting application in channel assignment problem and in radio technolo- gies. Moreover, this concept can be applied in security based community design. For the basic terminologies we refer to Chartrand et al. [1993]. 2 Preliminaries Theorem 2.1. Let u be any vertex of a connected graph G. (i) Every end-vertex of G other than the vertex u (whether u is an end-vertex or not) belongs to every u-square free detour set. (ii) No cut-vertex of G belongs to any dn �fu -set. Theorem 2.2. For any vertex u in a non-trivial connected graph G of order n,1 ≤ dn �fu (G) ≤ n−1. 287 Forcing vertex square free detour number of a graph Theorem 2.3. Let G be a connected graph. (i) If G is the complete graph Kn, then dn�fu (G) = 1 for every vertex u in Kn. (ii) If G is the complete bipartite graph Km,n(2 ≤ m ≤ n) with partitions X and Y , then dn �fu (G) = { m−1 if u ∈ X n−1 if u ∈ Y (iii) If G is the cycle Cn, then dn�fu (G) = 1for every vertex u in Cn. (iv) For a wheel Wn(n ≥ 4), dn �fu (Wn) =   ⌈ n−1 3 ⌉ if u ∈ K1. n ≥ 4 2 if u ∈ Cn−1, n ≥ 6 1 if u ∈ Cn−1, 4 ≤ n ≤ 5 3 Forcing vertex square free detour number of a graph Even though every connected graph contains a vertex square free detour set, some connected graph may contain several vertex square free detour sets. For each minimum vertex square free detour set Su in a connected graph there is always some subset T of Su that uniquely determines Su as the minimum vertex square free detour set containing T such forcing subsets are considered in this section. Definition 3.1. Let u be any vertex of a connected graph G and Su be a dn�fu -set of G. A subset Fu ⊆ Su is called a u-forcing subset for Su if Su is the unique dn �fu -set consisting of Fu. The u-forcing subset for Su of minimum cardinality is a minimum u-forcing subset of Su. The forcing u-square free detour number of Su, denoted by fdn�fu (Su) is the order of a minimum u-forcing subset for Su. The forcing u-square free detour number of G is fdn �fu (G) = minfdn �fu (Su) where the minimum is considered over all dn �fu -sets Su in G. Example 3.1. For the graph G shown in Figure 1, the only dn �fv1 -sets are {v2,v4}, {v2,v5},{v3,v4} and {v3,v5}. Hence fdn�fu (G) = 2. Also dn�fu (G) = 2 and fdn �fu (G) = 1 for u = v3 and v4 in G. Moreover v5 and v4 are the unique vertex square free detour sets for vertices v2 and v5 respectively and so fdn�fu (G) = 0 for u = v2,v5. 288 G. Priscilla Pacifica and K. Christy Rani Figure 1: G The following theorem follows from the definitions of vertex square free de- tour number and forcing vertex square free detour number of a graph G. Theorem 3.1. For any vertex u in a connected graph G, 0 ≤ fdn �fu (G) ≤ dn �fu (G). Proof. Let u be any vertex of G. From the definition of fdn �fu (G), we find that fdn �fu (G) ≥ 0, consider a dn �fu -set Su in G. We have fdn�fu (G) = min{fdn �fu (Su) : Su is a dn�fu -set in G } and so fdn�fu (G) ≤ dn�fu (G). Hence 0 ≤ fdn �fu (G) ≤ dn �fu (G). Now, we characterize the graph G for which the bounds in Theorem 3.1 are reached and the graph for which fdn �fu (G) = 1. Theorem 3.2. Let u be any vertex of a connected graph G. Then (i) fdn �fu (G) = 0 if and only if G has a unique dn �fu -set, (ii) fdn �fu (G) = 1 if and only if G has at least two dn �fu -sets one of which is a unique dn �fu -set containing any one of its elements, (iii) fdn �fu (G) = dn �fu (G) if and only if no dn �fu -set of G is the unique dn �fu - set containing any of its proper subsets. Proof. (i) Let fdn �fu (G) = 0. Then, fdn �fu (Su) = 0 where Su is any dn�fu - set by definition and so the empty set is the minimum u-forcing subset for Su. Since the empty set φ is a subset of every set we have Su is the unique minimum u-forcing subset of G. The converse of this Theorem is obvious. 289 Forcing vertex square free detour number of a graph (ii) Let fdn �fu (G) = 1. Then by (i),G has at least two fdn �fu -sets. Also, since fdn �fu (G) = 1, there is a singleton subset F of a dn �fu -set Su of G such that F is not a subset of any other dn �fu -set of G. Thus Su is the unique dn �fu -set containing one of its elements. The converse is obvious. (iii) Let fdn �fu (G) = dn �fu . Then fdn �fu (Su) = dn�fu (G) for every dn�fu -set Su in G. By Theorem 2.1, dn�fu (G) ≥ 1 and so fdn�fu (G) = 1. Also by (i), G has at least two dn �fu -sets and hence the empty set φ is not a u-forcing subset of any dn �fu -set Su of G is unique dn�fu -set which consists of its proper subsets. Theorem 3.3. Let G = (V,E) be a connected graph and let S∗u be the set of all u-square free detour vertices of G. Then fdn �fu (G) ≤ dn �fu (G)−|S∗u|. Proof. Let Su be any square free detour basis of G. Then dn�fu (Su) = |Su|,S ∗ u ⊆ Su and Su is the unique square free detour basis containing Su − S∗u. Thus fdn �fu (G) ≤ |Su −S∗u| = |Su|− |S∗u| = dn�fu (G)−|S ∗ u|. Remark 3.1. The bound in Theorem 3.3 is sharp. For the graph G given in Figure 2, fdn �fv1 (G) = 0, |S∗v1| = 2 and dn�fv1 (G) = 2. Also, the inequality in Theorem 3.3, can be strict. For the graph G given in Figure 1, fdn �fv3 (G) = 1, |S∗v3| = 0 and dn �fv3 (G) = 2. Thus fdn �fv3 (G) < dn �fv3 (G)−|S∗v3|. Figure 2: G Theorem 3.4. Let G be a connected graph and let = be the set of relative com- plements of the minimum u-forcing subsets in their respective minimum u-square free detour sets in G. Then ∩F∈=F is the set of all u-square free detour vertices of G. Proof. Let S∗u be the set of all u-square free detour vertices of G. We claim that S∗u ⊆∩F∈=F . Let x ∈ S∗u. Then x is a u-square free detour vertex of G so that x belongs to every u-square free detour set Su of G. Let T ⊆ Su be any minimum u-forcing subset for any u-square free detour basis Su of G. We claim that x /∈ T . 290 G. Priscilla Pacifica and K. Christy Rani If x ∈ T , then T ′ = T −{x} is a proper subset of Su is the unique u-square free detour containing T ′ so that T ′ is a u-forcing subset for Su with |T ′| < |T|, which is a contradiction to T is a minimum u-forcing subset for Su. Thus x /∈ T and so x ∈ F , where F is the relative complement of T in Su. Hence x ∈∩F∈=F so that S∗u ⊆∩F∈=F . Conversely, let x ∈ ∩F∈=F . Then x belongs to the relative complement of T in Su for every T for every Su such that T ⊂ Su, where T is a minimum u-forcing subset for Su. Since F is the relative complement of T in Su,F ⊂ Su and so x ∈ Su for every Su so that is a u-square free detour vertex of G. Thus x ∈ S∗u and so ∩F∈=F ⊂ S∗u. Hence S∗u ∩F∈= F . Theorem 3.5. Let u be any vertex of a connected graph G and let Su be any dn�fu -set of G. Then (i) No u-square free detour vertex belongs to any minimum u-forcing subset of Su. (ii) No cut-vertex of G belongs to any minimum u-forcing subset of Su. Proof. (i) The proof follows from the first part of Theorem 3.4. (ii) Since any minimum u-forcing subset of Su is a subset of Su, the proof follows from Theorem 2.1(ii). Corolary 3.1. Let u be any vertex of a connected graph G. If G contains l end- vertices, then fdn �fu (G) ≤ dn �fu (G)− l + 1. Proof. This follows from Theorems 2.1(i) and 3.5(i). Remark 3.2. The bound in Corollary 3.1 is sharp. For a tree T with l end- vertices, fdn �fu (G) = dn �fu (G)− l + 1 for any end-vertex u in T . Theorem 3.6. Let G be any connected graph of order n. Then (i) If G is a tree with l end-vertices, then fdn �fu (G) = 0 for every vertex l in G. (ii) If G is the complete graph Kn, then fdn �fu (G) = { 0 if n = 4 n otherwise 291 Forcing vertex square free detour number of a graph (iii) If G is the complete bipartite graph Km,n(2 ≤ m ≤ n), with partitions X and Y , dn �fu (Km,n) = 0 for every vertex u in Km,n. (iv) If G is the cycle Cn, then fdn �fu (G) = { 0 if n = 4 1 otherwise (v) If G is the wheel Wn, then fdn �fu (Wn) =   0 if n = 5,u ∈ K1 1 if n = 4,u ∈ Wn and n ≥ 6,u ∈ Cn−1⌈ n−1 3 ⌉ if n ≥ 6,u ∈ K1. Proof. (i) By the fact that dn �fu (G) = l−1 or dn �fu (G) = l when u is an end- vertex or not an end-vertex. Since the set of all end-vertices of a tree is the unique dn �fu -set, the result follows from Theorem 3.2(i) that fdn �fu (G) = 0. (ii) By Theorem 2.3(i) for the complete graph K4, Su consists of the antipodal vertex of u. Since the set of antipodal vertex is unique for K4, the result follows from Theorem 3.2(i) that fdn �fu (G) = 0. For Kn(n 6= 4) it follows from Theorem 2.3(i), that Su consists of exactly one vertex of V −{u}. Thus there exist n−1 distinct vertices other than u in Kn. Then the result follows from Theorem 3.2(ii) that fdn �fu (G) = 1. (iii) By Theorem 2.3(ii), for Km,n(2 ≤ m ≤ n) with partitions X,Y with |X| = m and |Y | = n, we have dn �fu (G) = m−1 or dn �fu (G) = n−1 according to whether the vertex u lies in X or Y . Since the dn �fu -set Su is unique in both the cases, the result follows from Theorem 3.2(i) that fdn �fu (G) = 0. (iv) By Theorem 2.3(iii) for C4,dn�fu -set Su consists of the antipodal vertex of u. Thus we observe that Su is unique and so fdn�fu (G) = 0 by Theorem 3.2(i). By Theorem 2.3(iii), for an even cycle Cn(n 6= 4),Su consists of exactly one vertex which is antipodal or adjacent to u. Also, for an odd cycle Cn(n ≥ 3)dn�fu -set Su contains exactly one vertex which is adjacent to u. Since there exist two adjacent vertices for an odd cycle and in addition an antipodal vertex for an even cycle we have fdn �fu (G) = 1. 292 G. Priscilla Pacifica and K. Christy Rani (v) By Theorem 2.3(iv), for Wn = K1 + Cn−1(n ≥ 5) a dn�fu -set Su consists of ⌈ n−1 3 ⌉ vertices of the rim Cn−1 of Wn, where u is a central vertex of Wn that is in K1 called as hub. Thus there exist three different dn�fu -sets with ⌈ n−1 3 ⌉ vertices. Therefore, from Theorem 3.2(ii) the result follows that fdn �fu (G) = ⌈ n−1 3 ⌉ for the central vertex of Wn(n ≥ 5). When u is a vertex on Cn−1 of Wn by Theorem 2.3(iv), Su contains exactly one adjacent or antipodal vertex on Cn−1 with the hub of the wheel, accord- ing as n − 1 is odd or n − 1 is even. Thus there are two adjacent vertices for a vertex on an odd cycle and an antipodal vertex besides two adjacent vertices for a vertex on even cycle. Hence the result follows from Theorem 3.2(ii) that fdn �fu (G) = 1 for u ∈ Cn−1(n ≥ 6). By Theorem 2.3(iv) for W4,Su consists of exactly one adjacent vertex for every u ∈ W4. Thus there are n− 1 such dn�fu -sets, for the vertices of W4 are adjacent to each other. Hence by Theorem 3.2(ii), we have fdn �fu (G) = 1. Also, for W5,Su contains two antipodal vertices of C4 where u is the central vertex of W5. Since there exist two different Su with distinct pair of antipo- dal vertices of C4, from Theorem 3.2(iii), the result follows that fdn�fu (G) = dn �fu (G) = 2. Furthermore, when u is a vertex on the rim of W5,Su con- sists of the antipodal vertex of u. Since there is only one antipodal vertex for any vertex u on C4 of W5, we have unique Su for all vertices on the rim of W5. Hence the result follows from Theorem 3.2(i) that fdn�fu (G) = 0. Theorem 3.7. For every pair α,β of positive integers with 0 ≤ α ≤ β and β ≥ 2, there exists a connected graph G with fdn �fu (G) = α and dn �fu (G) = β for some vertex u in G. Proof. We consider two cases. Case 1: Let α = 0. Let G be any tree with β + 1 end-vertices. Then for an end- vertex u in G,fdn �fu (G) = 0 by Theorems 3.2(i) and 3.5(i). Case 2: Let α ≥ 1. For each i(1 ≤ i ≤ α), let Di6 be a Dutch Windmill graph consisting of i copies of C6 : u,pi,qi,ri,si, ti,u. Let H be a graph obtained by adding α new vertices r′1,r ′ 2, ...,r ′ α and joining each r ′ i(1 ≤ i ≤ α) to both the vertices qi and si of Di6(1 ≤ i ≤ α). 293 Forcing vertex square free detour number of a graph Let K1,β−α be the star with common vertex wo and let W = {w1,w2, ...,wβ−α} be the set of all end-vertices of K1,β−α. Let G be the required graph produced by identifying the vertex u of Di6 with the common vertex wo of K1,β−α as pictured in Figure 3. Figure 3: G First we show that dn �fu (G) = β for some vertex u in G. By the fact that every dn �fu -set of G contains W and exactly one vertex from each C6 of Di6(1 ≤ i ≤ α). Then dn�fu (G)(β − α) + α and so dn�fu (G) = β. Let Su = W ∪ {x1,x2, ...,xα}, where xj = pj or tj of Ci6(1 ≤ i ≤ α). Clearly Su is a dn�fu -set of G and so (G) ≤ |Su| = (β−α)+α = β. Thus dn�fu (G) = β. Next we show that fdn �fu (G) = α. Since dn �fu (G) = β, we find that every dn �fu -set of G consists of W and exactly one vertex from each C6 of Di6(1 ≤ i ≤ α). Let F ⊆ Su be any minimum u-forcing subset of Su. Then By Theorem 3.5(ii),F ⊆ Su − W and so |F| ≤ α. If |F| < α then there is a vertex yj of Ci6(1 ≤ i ≤ α) distinct from xj(1 ≤ i,j ≤ α). Then S′u = (Su − xj) ∪ yj is also a minimum u-forcing subset containing F such that xj /∈ F . Thus Su is not a unique u-square free detour set which consists of F and so F is not a minimum u-forcing subset of Su. Thus fdn�fu (G) = α. 294 G. Priscilla Pacifica and K. Christy Rani 4 Conclusion In this paper, we computed the forcing vertex square free detour number of some standard graphs. We discussed the characteristics of the forcing vertex square free detour sets. Also, the relationship between the vertex square free detour number and the forcing vertex square free detour number has been exhib- ited. In future, this concept can be extended to edge related parameter. To derive similar results in the context of some other variants of detour number is the open area of research. References A. M. Ali and A. A. Ali. The connected detour numbers of special classes of connected graphs. Journal of Mathematics, 2019, 2019. G. Chartrand, G. L. Johns, and S. Tian. Detour distance in graphs. In Annals of discrete mathematics, volume 55, pages 127–136. Elsevier, 1993. G. Chartrand, G. L. Johns, and P. Zhang. The detour number of a graph. Utilitas mathematica, 64, 2003. S. S. Ramalingam, I. K. Asir, and S. Athisayanathan. Vertex triangle free detour number of a graph. Mapana Journal of Sciences, 15(3):9–24, 2016. K. C. Rani and G. P. Pacifica. Outer independent square free detour number of a graph. Ratio Mathematica, 44:309–315, 2022. A. Santhakumaran and S. Athisayanathan. On the connected detour number of a graph. Journal of Prime research in Mathematics, 5:149–170, 2009. A. Santhakumaran and S. Athisayanathan. Forcing edge detour number of an edge detour graph. Journal of Prime Research in Mathematics, 6:13–21, 2010. P. Titus and P. Balakrishnan. The forcing vertex detour monophonic number of a graph. AKCE International Journal of Graphs and Combinatorics, 13(1): 76–84, 2016. 295