SciresolSciresolhttps://indjst.org/author-guidelinesIndian Journal of Science and Technology0974-564510.17485/IJST/v16i1.1875Research ArticleConnected Restrained Detour Number of a GraphPacificaG Priscilla1RaniK Christychristy.agnes@gmail.com2RamalingamS Sethu3Department of Mathematics, St. Mary’s College (Autonomous)Thoothukudi , 628001IndiaReg. No.: 20122212092002, PG and Research Department of Mathematics, St. Mary’s College (Autonomous),Manonmaniam Sundaranar UniversityAbishekapatti, Tirunelveli, 627012IndiaDepartment of Mathematics, St. Xavier’s College (Autonomous) 627002India5120231613217102022301020222022Abstract

Objectives: To find the connected restrained detour number for standard graphs and mesh graphs. Methods: By determining the connected restrained detour set with minimum cardinality, the connected restrained detour number of a graph is investigated. Findings:We study that the connected restrained detour number of the graphs is altered when we add pendent vertices. The minimum and maximum degree vertices of a graph are deleted and the connected restrained detour number of the mesh graph is computed. Novelty: Finding the detour path plays a vital role in the network-based systems. Planning the largest route that is connected and restrained is essential in business, industries and radio technologies.We introduce the new concept of connected restrained detour number.We also exhibit the bounds for the connected restrained detour set of a graph.

Connected detour number of a graph developed from the notion of detour number was studied by Ali, Ahmed M, and Ali A. Ali^{ }1. Various parameters of detour number were established by John J, Sunil Kumar VR, Sethu Ramalingam S and Athisayanathan S ^{2, 3, 4}. In 2020, Palani K, Shanthi P, Nagarajan A. established the restrained detour concept ^{5, 6. }Santhakumaran AP, Titus P, Ganesamoorthy K. defined the minimal connected restrained monophonic sets in graphs 7 . In this study, we introduce the connected restrained detour number denoted bydncrG. The connected restrained detour number for some standard graphs and mesh graphs is studied. We denote the vertices with minimum degree and maximum degree by δ-vertices and ∆-vertices in a graph M. We discuss the effect of the addition of pendent vertices to the δ-vertices of mesh M. We also investigate the connected restrained detour number of derived graphs obtained from the mesh graphs by deletion of the pendent vertices from the δ-vertices of the mesh M.

Let G=(VG,EG) be a connected finite simple graph with order n≥2.

Methodology

Definition 2.1. Any set R⊆V(G) is a connected restrained detour set if

(i) 𝑅 is a detour set of G

(ii) ⟨R⟩ is connected and

(iii) no isolated vertices exist in <V(G)-R>

Definition 2.2. The connected restrained detour number, dncr(G) is the minimum cardinality of connected restrained detour set of G

Definition 2.3. A connected restrained detour set with cardinality dncr(G) is called the minimum connected restrained detour set [dncr-set] of G.

Example 2.4. For G1 shown in Figure 1 , R'=z2,z3,z6,z7,R''=z2,z3,z6,z8 and R'''=z1,z2,z3,z6_{ }are the dncrsets of G1. Hence dncrG1=4. Thus there can be many dncrsets for any graph G.

G1

Results and Discussion

Theorem3.1.For a cycle Cnn≥3,dncrCn=2.

Proof. Consider a cycle Cnwith VCn=n. If R={y,z} is a set of vertices that are adjacent in Cn, then all the vertices in VCn lie on some y-z detour. Since y and z are adjacent, <R> is connected and <VCn-R> has no isolated vertices. Hence R is a dncr-set and dncrCn=2.

Theorem 3.2. For a path Pnn≥2,dncrPn=n.

Proof. Consider a path Pn of order n. Let R be a set of end-vertices. Then all the vertices of Pn lie on some detour joining those two end-vertices of R.Since the vertices of R are not connected, <R> is also not connected but <VPn-R> has no isolated vertices. Thus R is not a dncr-set. Therefore, R must contain all the internal vertices to generate adncr-set. Thus dncrPn=n.

Remark 3.3. By Theorem 3.1, for a cycle Cn, a set of any two adjacent vertices is a detour set and also adncr-set. Hence dn(Cn)=dncr(Cn)=2.Thus

2=dn(G)=dncr(G)<n, for Cn

By Theorem 3.2, for the path Pnof ordern,dncr(Pn)=n.

2=dn(G)<dncr(G)=n, for P2

For the given graph G1 of order 8 as in Figure 1, R=z2,z3,z7 is a minimum detour set.

Hence dnG=3. Thus

2<dn(G)<dncr(G)<n, for G1

Observation 3.4. From (1), (2) and (3) of Remark 3.1, we obtain the bound for adncr-set.

2≤dnG≤dncrG≤n.

The following theorems exhibit the dncr-set for the cartesian product of any two paths Paand Pb, which is known as mesh graph M=Pa□Pb and their derived graphs.

Theorem 3.5. Let Paand Pb be the paths of order aandb. Then dncrPa□Pb=2.

Proof. Let M=Pa□Pb be a mesh, where

VPa=h1,h2,…,haand VPb=h1*,h2*,h3*,…,hb*;

VPa□Pb=hi,hj*=hij:1≤i≤a,1≤j≤b;hi∈Pa,hj*∈Pb.

Then VPa□Pb=ab. Let R be a set of two vertices, which are adjacent in the boundary of the mesh M. We consider four cases.

Case 1.Let a and b be even. Clearly, every vertex of M lies on either the P':hk1-hk+11 or P'':hkb-hk+1bdetour, similarly on either P''':h1l-h1l+1 or P'''':hrl-hrl+1detour for some k,l1≤k≤a-1;1≤l≤b-1. Suppose S =hk1,hk+11. Then the vertices of M lie on P':hk1-hk+11 detour 1≤k≤b-1. When k=1,

Similarly, we can derive the detour path of P'',P''' and P'''', where 2≤k≤a-1;1≤l≤b-1.

Case 2. Let aand b be odd. Obviously, every vertex of M lies on either the P':hk1-hk+11 or P”:hkb-hk+1bdetour, similarly on either P''':h1l-h1l+1 or P'''':hal-hal+1detour for some k,l1≤k≤a-1;1≤l≤b-1. Suppose R =h1l-h1l+1. Then the vertices of M lie on either P1':hk1-hk+11 detour or P2':hk1-h1≤k≤a-1. If k=1,

Similarly, we find two different detour paths of {P^{''},P}^{'''}and P'''',\;where 2\leq k\leq a-1;\;1\leq l\leq b-1.\;

Case 3.Let a be even. Clearly, every vertex of M lies on P^'or P''\;detour, where P^':h_{k1}-h_{\left(k+1\right)1} and P'':\;h_{kb}-h_{\left(k+1\right)b}. Then R=\left(h_{k1},\;h_{\left(k+1\right)1}\right\} or R =\left(h_{kb},\;h_{\left(k+1\right)b}\right\}. As in Case 1, consider P^':h_{11}-h_{21}, then

In the same manner, we can find different detour paths of P^'\;and P^{''},\;where 2 \leq k \leq a-1

Case 4.Let b be even. Let R =\left(h_{al},h_{a\left(l+1\right)}\right\} or R =\left(h_{al},h_{a\left(l+1\right)}\right\}. Then the vertices of M lie on P^{'''}:h_{1l}-h_{1\left(l+1\right)} or P'''':\;h_{al}-h_{a\left(l+1\right)}\;detour (1 \leq l \leq b-1)

In the same manner, we can find different detour paths of P^{'''}and P'''',\;where \;2\leq l\leq\alpha-1.\;

All the above four cases show that R is connected and <V\left(P_{a\;}\square{\;P}_b\right)-R> has no isolated vertices and so R is the dn^{cr}-set. Hence dn^{cr}\left(G\right)=2.

Remark 3.6. Let {M=P}_{a\;}\square{\;P}_b be the mesh as shown in Figure 2 . If b=2, then by Theorem 3.5 P_{a\;}\square\;P_2 is a ladder graph L_a\;and dn^{cr}\left(L_a\right)=2.

Theorem 3.7. Let M=P_{a\;}\square{\;P}_b be a mesh of order ab\left(2\leq a\leq b\right). Let M^{+p\;}be the graph expanded from M by adding a pendent vertex to the \delta-vertices of M. Then dn^{cr}(M^{+p\;}\;)=2\left(a+b+2\right).

Proof. Let M^{+p\;} be a graph derived from\;{M=P}_{a\;}\square{\;P}_b\left(2\leq a\leq b\right) by adding a pendent vertex to the \delta-vertices of M. Let R^{p\;}be a set of all pendent vertices of M^{+p}. Then R^{p\;}=\left(p_i:1\leq i\leq4\right\}. Now obviously, R^{p\;} is a dn^{cr}-set but not a connected restrained detour set by Theorem 3.4. Therefore, a dn^{cr}-set R must contain all the pendent vertices and the boundary vertices. Suppose R=R^{p\;}\cup R^b, where R^{b\;}is the set of all boundary vertices. Then \left(R\right|=\left(R^{p\;}\right|+\vert\left(h_{ik,}\;h_{lj}\right\}\vert=4+2(a+b)=2\left(2+a+b\right). Hence all the vertices of M^{+p\;} lie on some detour joining the vertices of R. Moreover, R is connected and <V\left(M^{+p\;}\right)-R> has no isolated vertices. Hence dn^{cr}{(M}^{+p\;})=2\left(a+b+2\right).

Theorem 3.8. Let M^{+kp\;} be the graph obtained from M=P_a\square{\;P}_b\left(2\leq a\leq b\right) by the addition of k-pendent vertices at each \delta-vertices of M. Then dn^{cr}\left(M^{+kp\;}\right)=2\left(a+b+2k\right).

Proof. Let\;M^{+kp\;} be a graph with \left(V\left(M^{+kp\;}\right)\right|=ab+4k. Let R^{p\;}be a set of all pendent vertices added to M. Then \left(R^{p\;}\right|=4k. Since all the vertices of M^{+kp\;}lie on some detour joining the pendent vertices in R^p, R^{p\;}is the minimum detour set. Since M^{p\;}is not connected, we consider the sets R\;and R^b, the set of all boundary vertices. Then R^{b\;}=\left(\left(h_{ik}:1\leq k\leq b;\;i=1,\;a\right\}\cup\{h_{lj}:\;1\leq l\leq a;\;j=1,\;b\right\}.\;Suppose R=R^{p\;}\cup R^b. Therefore, |R|=\left|R^p\right|+\left|\left\{h_{i k}, h_{l j}\right\}\right|=4 k+2(a+b)=2(a+b+2 k) Since R is connected and <V\left(M^{+kp\;}\right)-R> has no isolated vertices, R is a dn^{cr}-set. Therefore dn^{cr}{(M}^{+kp\;})=2\left(a+b+2k\right).

Now, we discuss how the connected restrained detour number is altered by deleting the \delta-vertices and \triangle-vertices of the mesh graph M.

Theorem 3.9. Let M^{-\delta} be the graph derived from M=P_a\;\square{\;P}_b\left(2\leq a\leq b\right) by deleting the \delta-vertices of M. Then -

Proof. Let M=P_a\;\square{\;P}_b\left(2\leq a\leq b\right). Let M^{-\delta} be the graph derived by deletion of \delta-vertices of M. Then we consider three cases.

Case 1. Let M=P_a\square{\;P}_b\left(a=b\right). Consider R to be a connected restrained detour set of M^{-\delta}. We have two subcases.

Subcase 1.Let a=b=2.\;Since all the vertices of {V(P}_{2\;}\square{\;P}_2) are the \delta-vertices, the graph M^{-\delta} is the null graph. Hence dn^{cr}\left(M^{-\delta}\right)=0.

Subcase 2. Let a=b=3.\;Then all the vertices of M^{-\delta} become the elements of\;R and so R=\left\{h_{12}, h_{21}, h_{22}, h_{23}, h_{32}\right\} is a dn^{cr}-set. Hence dn^{cr}\left(M^{-\delta}\right)=5.

Case 2. When a\neq3, we have two subcases.

Subcase 1. Let\;a=2\;and b\geq3. When b=3,\;the graph M^{-\delta} derived from{\;P}_{a\;}\square{\;P}_b becomes K_2. Hence R=V(M^{-\delta}),\;\;dn^{cr}\left(M^{-\delta}\right)=2.\; When b\geq4,{\;M}^{-\delta}\;is the Ladder graph{\;L}_{a-2}=P_{a-2}{\square\;P}_2. Hence dn^{cr}\left({\;L}_{a-2}\right)=2.

Subcase 2. If a\geq4 and b\geq3, then R=\left(h_{1q},\;h_{(q+1)1}\right\} or \left(h_{qb},\;h_{(q+1)b}\right\}, where 2\leq q\leq b-2, is a set of any two adjacent vertices. Since all the vertices of M^{-\delta} lie on some detour joining the vertices of R,\;it is a minimum detour set. Moreover, R is connected and <V(M^{-\delta}\;)-R> has no isolated vertices. Thus R becomes the dn^{cr}-set of M^{-\delta}and so dn^{cr}\left(M^{-\delta}\right)=2.

Case 3. Leta=3,b\geq4.Since M^{-\delta} is a graph obtained from M by deletion of \delta-vertices, produces the pendent vertices h_{21} and h_{2b} of M^{-\delta}. Then the dn^{cr}-set R consists of the pendent vertices and all the internal vertices of h_{21}-h_{2b} detour. Thus\;R=\left(h_{21},h_{22},\;h_{23},\dots,h_{2b}\right\} and so dn^{cr}\left(M^{-\delta}\right)=b.

Theorem 3.10. Let M^{-\triangle} be the graph derived from M=P_a\square{\;P}_b(2\leq a\leq b) by deleting the \triangle-vertices of M. Then -

Proof. Let M=P_a\square{\;P}_b(2\leq a\leq b) be a mesh. Let M^{-\triangle\;}be a graph derived from M by the deletion of \triangle-vertices of M. Let R be the dn^{cr}-set of M^{-\triangle\;}. We have two cases.

Case1: Let r=2. Consider the two subcases.

Subcase 1. Whens=2, the graph M^{-\triangle} derived from{\;P}_2\square{\;P}_2 is the null graph. Since the \triangle-vertices are also the \delta-vertices of M, the result follows from subcase 2 of case1of Theorem 3.6 that dn^{cr}\left(M^{-\triangle}\;\right)=0.

Subcase 2. Let b>2. Since the boundary vertices of degree 3 are the \triangle-vertices of {\;M=P}_2\square{\;P}_b, the graph M^{-\triangle} becomes a disjoint union of two paths of order 2. In this case, we cannot have the detour set R that is connected. Therefore dn^{cr}\left(M^{-\triangle}\;\right)=0.

Case 2: Let a=b\geq3. Let R^{\triangle\;} be a set of all \triangle-vertices of M. Since\;\triangle(M)=4,R^{\triangle\;}=\left(h_{ij}:\;i\neq1,\;a;\;j\neq1,\;b\right\} and so \left(R^{\triangle\;}\right|=(a-2)\left(b-2\right). Thus M^{-\triangle\;}\;=M-R^{\triangle\;}. Hence {\vert M}^{-\triangle\;}\vert=\left(M\right|-\left(R^{\triangle\;}\right|\;=ab-(\left(a-2\right)\left(b-2\right))=2\left(a+b-2\right). Thus M^{-\triangle\;}\;is isomorphic to the even cycle of order 2\left(a+b-2\right). Thus M^{-\triangle\;}=C_{2\left(a+b-2\right).}\;Then by Theorem 3.1, R is a set of two adjacent vertices of M^{-\triangle\;} and so dn^{cr}{(M}^{-\triangle\;})=2.

Conclusion

In this study, we have computed the connected restrained detour number of some standard graphs, the mesh graphand their derived graphs. Derivation of similar results in the context of some other variants of detour number is an open area of research.

ReferencesAliAhmed MAliAli AThe Connected Detour Numbers of Special Classes of Connected GraphsJohnJKumarV R SunilThe open detour number of a graphRamalingamS SethuAthisayanathanSUpper triangle free detour number of a graphRamalingamSAthisayanathanSWeak edge triangle free detour number of a graphPalaniKShanthiPNagarajanARestrained Detour Domination Number of a GraphPalaniKShanthiPNagarajanATotal Restrained Detour Domination Number of a GraphSanthakumaranA PTitusPGanesamoorthyKMinimal connected restrained monophonic sets in graphs