Split Detour Monophonic Sets in Graph

M. MAHENDRAN1, R. KAVITHA2

1Department of Humanities and Science,

Rajalakshmi Institute of Technology,

Kuthambakkam Post, Chennai, 600 124,

INDIA

2Department of Mathematics and Statistics,

Faculty of Science and Humanities,

SRM Institute of Science and Technology, Kattankulathur Campus,

Chengalpattu, TamilNadu,

INDIA

Abstract: - A subset T  is a detourmonophonic set of G if each node (vertex) x in G contained in an p-q

detourmonophonic path where p, q  T.. The number of points in a minimum detourmonophonic set of G is

called as the detourmonophonic number of G, dm(G). A subset T  of a connected graph G is said to be a

split detourmonophonic set of G if the set T of vertices is either T = V or T is detoumonophonic set and V – T

induces a subgraph in which is disconnected. The minimum split detourmonophonic set is split

detourmonophonic set with minimum cardinality and it is called a split detourmonophonic number, denoted by

dms(G). For certain standard graphs, defined new parameter was identified. Some of the realization results on

defined new parameters were established.

Key-Words: - Distance, geodesic, monophonic path, detour, monophonic number, detourmonophonic

path, detourmonophonic number, split detourmonophonic number.

Received: August 19, 2023. Revised: December 21, 2023. Accepted: February 22, 2024. Published: April 9, 2024.

1 Introduction

In the whole paper, we assume finite, undirected and

connected graphs represented by G = (V,E), where

V denotes the set of vertices (nodes or points) and E

the set of edges (lines) (without loops or multiple

edges), with |V| = n and |E| = m respectively. For

basic concepts, we refer to [1]. The distance, [2],

d(p,q) in G is defined as the length of the shortest

path between p and q in G. A p-q path of length

d(p,q) is referred to as a p-q geodesic. A vertex x is

extreme if the neighbors of x induce a complete

graph. A set S  V (G) is termed a geodetic set of G

if every vertex of G lies on a x-y geodesic, where x

and y are in S. The cardinality of a minimum

geodetic set is known as the geodetic number of G,

denoted by g(G). The concept of geodetic numbers

was introduced and studied in [3], [4], [5].

In a path x1, x2, . . . , xn, an edge xixj with j ≥ i +

2 is termed a chord. For nodes p and q in G, a p-q

path is considered a monophonic path if this p-q

path is the chordless path. A monophonic set T of G

contains every vertex of G in the monophonic path

of some pair of points in T. The number of points in

the minimum monophonic set is called the

monophonic number and is denoted by m(G). This

concept was discussed in detail in [6], [7].

A split monophonic set T of the graph is T is

either equal to V or T is a monophonic set and the

subgraph [V – T] is disconnected. This concept was

studied in [8]. A p – q chordless path with

maximum length is known as a p – q

detourmonophonic path. A set T V is a

detourmonophonic set of graphs if every nodes x of

G contained in a p – q detourmonophonic path for

any nodes p and q in T. The detourmonophonic

number of the graph notated by dm(G), the number

of vertices in a minimum detourmonophonic set.

This concept was discussed in [9], [10].

A detour monophonic set T is connected if the

subgraph induced by T is connected. The number of

vertices in the minimum connected

detourmonophonic set is the connected

detourmonophonic number, denoted by dmc(G).

This concept was discussed in detail in [11]. The

concept of outer connected in detour was discussed

in detail in [12].

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2024.23.5

M. Mahendran, R. Kavitha

E-ISSN: 2224-2872

Volume 23, 2024

Result 1.1. [9], Every detourmonophonic set

contains all its extreme nodes of graph.

2 Split Detourmonophonic Number of

a Graph

Definition 2.1. A set T of vertices in a connected

graph G is a split detour monophonic set if either T

is a detour monophonic set and the subgraph

induced by V –T is disconnected or T = V . A split

detourmonophonic set with minimum cardinality is

a minimum splitdetour monophonic set and this

number is the split detourmonophonic number

dms(G).

Fig. 1: A graph with dxs(G) = 4

Example 2.2. In a given G, Figure 1, S = {v1, v5,

v6} is a minimum detourmonophonic set and dm(G)

= 3. It was noticed that V − S is not disconnected.

Let S1 = {v2, v8, v5, v6}. S1 is minimum split

detourmonophonic set and dms(G) = 4.

From Example 2.2, it is observed that detour

monophonic number differs from the split detour

monophonic number.

Result 2.3. Split detour monophonic set of any

graph G may or may not contain the cutvertex of the

given graph.

Proof. We prove this result by inspecting Example

2.2, it is observed that the sets S1 = {v2, v5, v6, v8},

and S2 = {v1, v3, v5, v6} are the split detour

monophonic sets. Also, v3 is cutvertex of G and v3 

S2 but v3  S1. Hence, the cutvertex need not be a

member of the split detour monophonic set.

Let us consider another example to express that dm,

dms, dmc are different

Fig. 2: A graph with dm(G) ≠ dms(G) ≠ dmc(G)

Example 2.4 In above graph Figure 2, T = {v1, v5,

v6, v7} - minimum detourmonophonic set and dm(G)

= 4. Also, the set T1 = {v1, v3, v5, v6, v7} is a

minimum split detourmonophonic set, dms(G) = 5.

Clearly, T1 = {v1, v2, v3, v4, v5, v6, v7} is the

minimum connected detourmonophonic set, dmc(G)

= 7. Hence, the dm(G) ≠ dms(G) ≠ dmc(G).

We know that the detourmonophonic set is

contained in split detourmonophonic set and this

implies dm(G) ≤ dms(G). Also, a split

detourmonophonic set is contained in a connected

detourmonophonic set. Hence, dms(G) ≤ dmc(G).

Combining the above result, we can state the

theorem as

Result 2.5 For graph with order n, 2 ≤ dm(G) ≤

dms(G) ≤ dmc(G) ≤ n, dms(G) ≠n − 1.

Result 2.6 Every extreme node of the graph in split

detourmonophonic set.

Proof. By Result 1.1, Every extreme vertex

contained in the detourmonophonic set and also,

every detourmonophonic set is a subset of the split

detourmonophonic set. Hence every extreme vertex

belongs to a split detourmonophonic set.

Corollary 2.7 In complete graph Kn(n ≥ 2), dms(Kn)

= n.

Remark 2.8 Converse of the above fact need not be

true. For the graphs P3 and P4, it is clear that dms(P3)

= 3 and dms(P4) = 4.

Result 2.9 For any cycle G = Cn(n ≥ 4), dms(G) =





Proof. Let the cycle G = Cn(n ≥ 4) be Cn : v1, v2, . . ,

vn, v1 of order n. For n even.

the set S = {v1, vn/2+1} is a minimum split

detourmonophonic set. In general, we can generate 



minimum split detourmonophonic sets which can be

represented as Si = {vi, vn/2+i} where i = 1, 2, . . . ,

n/2 and dms(G) = 2.

For n odd. On verifying the set S = {v1, 

,

}is

a smallest split detourmonophonic set. In general,

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2024.23.5

M. Mahendran, R. Kavitha

E-ISSN: 2224-2872

Volume 23, 2024

we can generate n minimum split detourmonophonic

which can be represented as Si = {vi, vj , vj+1} such

that dm(vi, vj) = 

where 1 ≤ i ≤ n and 1 ≤ j ≤ n.

Hence dms(G) = 3.

Result 2.10 For any path G = Pn(n ≥ 5), dms(G) =

Proof. Consider the Path Pn = v1v2v3 . . . vn−1vn. On

the view, the set S = {v1, vn} forms minimum

detourmonophonic set, dm(G) = 2. Notified that Si

= {v1, vi, vn} where d(v1, vi) ≥ 2 and d(vi, vn) ≥ 2 is a

smallest split detourmonophonic set. Hence dms(G)

= 3.

Result 2.11 For G = Kp,q(2 ≤ p ≤ q), dms(G) =p.

Proof. Let X = {x1, x2, . . . , xp} and Y = {y1,y2, . . .

,yq} be the partite sets of G. It is seen that the set S =

X forms a split detourmonophonic set with smallest

cardinality and so dms(G) = |U| = p.

Result 2.12 For Wn = K1+Cn−1(n ≥ 5), dms(Wn)

=



Proof. Let Wn = K1 + Cn−1(n ≥ 5), K1 = {x}, Cn−1 :

v1v2v3 ... ,vn−1vnv1 be the wheel of order n. For n

even. It is noticed that the set S = {v1,vn/2 +1,x} is a

minimum split detourmonophonic set. In general,

we can generate  minimum split

detourmonophonic sets which can be represented as

Si = {vi ,vn/2 +i, x} where i = 1, 2,... ,n/2 and dms(Wn)

= 3. For n odd. Clearly the set S = {v1, v (n+1)/ 2 ,v

(n+3)/2 , x} is a minimum split detourmonophonic set.

In general, we can generate n minimum split

detourmonophonic which can be represented as Si =

{vi ,vj , vj+1, x} such that dm(vi ,vj ) = (n−1)/2 where

1 ≤ i ≤ n and 1 ≤ j ≤ n. Hence dms(Wn) = 4.

Open Problem 2.13 Can you find an interconnected

undirected circuit G for which dms(G) = n.

The concept of a split detourmonophonic set can be

applied in one of the computational intelligence

methods namely neural network as witnessed in [13]

and also our new design could be facilitated in

graph neural network which is studied in [14]. The

application of our new design can be evolved in

[15], [16].

The concept of a split detourmonophonic set may be

applied in artificial intelligence and further can be

studied in [17], [18]. [19].

3 Some Existence Results

Result 3.1 There exists interconnected undirected

circuit G of order n, as arbitrary dms(G) = k and

dmc(G) = k + 1 where n, k integers with 2 < k < n,

Proof. Let P3 : u1u2u3 be the path of order 3. Now

join the vertices v1,v2,... ,vn−k to u1 as well as with u3.

Further, add k − 3 vertices such as w1,w2,w3,... ,wk−3

to the vertex vn−k. Hence, the desirable graph G of

order n as given in Figure 3 is obtained.

It is noticed that S = {w1,w2,... ,wk−2} does not

form a split detourmonophonic set which is set of

all extreme vertices. Let S1 = S  {u1,u2}. Notified

that S1 is the smallest split detourmonophonic set

and so dms(G) = k.

Fig. 3: A graph G of order n, as arbitrary dms(G) = k

and dmc(G) = k + 1

But S1 is a disconnected detourmonophonic set.

Let S2 = S  {vn−k}. Now, the S2 becomes

connected. Hence dmc(G) = k + 1.

Result 3.2 There exits an interconnected undirected

circuit G of order n as an arbitrary dm(G) = a,

dms(G) = a + 1 and dmc(G) = a + 2 where a, n

integers with 5 ≤ a < n.

Proof. Let Kn−a−1,3 be a complete bipartite graph. Let

U = {u1,u2,u3,... ,un−a−1} and W = {w1,w2,w3} be the

partite sets of Kn−a−1,3. Now, joining a vertex x to

each vertex of U. Also, add a − 3 vertices say

v1,v2,... ,va−3 with the vertex x. As a result, we

obtained the desired graph as given in Figure 4 of

order n.

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2024.23.5

M. Mahendran, R. Kavitha

E-ISSN: 2224-2872

Volume 23, 2024

Fig. 4: A graph G of order n as an arbitrary dm(G) =

a, dms(G) = a + 1 and dmc(G) = a + 2

The set W = {v1,v2,v3,w1,w2,... ,wa−3} forms a

smallest detourmonophonic set, dm(G) = a. But the

subgraph [V – W] is not disconnected. Let W1 = W

 {x}. Now, the set W1 becomes a minimum split

detourmonophonic set. Hence dms(G) = a + 1.

Moreover, the subgraph induced by W2 = W1  {u1}

is connected. Therefore, W2 becomes smallest

connected detourmonophonic set, dmc(G) = a + 2.

Result 3.3 There is an interconnected undirected

circuit G of order n with dms(G) = a and dmc(G) = b

where n, a, b are integers with 3 ≤ a ≤ b ≤ n,

Proof. Let Pb−a+3: v1v2 ... vb−a+3 be the path of order

b−a+3. Let w1,w2,w3,... ,wn−b be a set of n − b

vertices. Now, join each vertex wi(1 ≤ i ≤ n − b)

with u1 and u3 and add the set of new vertices

y1,y2,... ,ya−3 with w1. Therefore, the desirable circuit

G with n vertices as shown in Figure 5.

Fig. 5: A graph G of order n with dms(G) = a and

dmc(G) = b

The extreme vertices set S = {y1,y2,...

,ya−3,vb−a+3} is not detourmonophonic set. Let S1 = S

 {v1, v3}. It observed that S1 is the unique smallest

split detourmonophonic set and dms(G) = a. Also,

the set S1 is not connected. Now, let S2 = S1  {w1,

v4, v5, ... , vb−a+2}. Observed S2 is the smallest

connected detourmonophonic set, dmc(G) = b.

4 Conclusion

The work contains a new parameter ‘split

detourmonophonic number’. It helps in a circuit or

network to find removal nodes in the longest

connecting path between two nodes so that it split

the circuit or network. Also, we studied the

relationship and realization between connected and

split of the longest path between nodes. This design

of the circuit may facilitate thedevelopment

algorithms in Locating Capacitors, [20], to split the

network and to one of step detection, [21], of fault

in the longest monophonic path by splitting the

network

Acknowledgement:

The authors wish to thank Dr. P. Titus and Dr. K.

Ganesamoorthy for their valuable suggestions to

develop this paper. Also, the authors wish to thank

the reviewers and editorial board for showing a new

direction of research work in the future.

References:

[1] Harary F., Graph Theory, Addison-Wesley,

1969.

[2] Buckley F. and Harary F., Distance in

graphs, Addison-Wesley, Redwood city, CA,

1990.

[3] Chartrand G., Palmer E. M. and Zhang P.,

The geodetic number of a graph: A survey,

Congr. Numer., 156 (2002), 37-58.

[4] Chartrand G., Harary F., Swart H. C., and

Zhang P., Geodomination in graphs, Bulletin

of the ICA, 31(2001), 51-59.

[5] Muntean R. and Zhang P., On geodomination

in graphs, Congr. Numer., 143(2000), 161-

174.

[6] Santhakumaran A. P., Titus P. and

Ganesamoorthy K., On the monophonic

number of a graph, J. Appl. Math.

Informatics, Vol. 32 (2014), No. 1 - 2, pp.

255 - 266.

[7] Titus P. and Ganesamoorthy K., The

connected monophonic number of a graph,

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2024.23.5

M. Mahendran, R. Kavitha

E-ISSN: 2224-2872

Volume 23, 2024

Graph and Combinatorics, Vol. 30 (1)

(2014), pp. 237-245.

[8] Mahendran M., Nithyaraj. R, Balaganesan P.

and Somasundari M., The Split Monophonic

Number of a Graph, Journal of Adv Research

in Dynamical Control Systems, Vol. 11, 01-

Special Issue, 2019.

[9] Titus P. and Ganesamoorthy K., On the

Detourmonophonic Number of a Graph, Ars

Combinatoria, 129, pp. 33-42, (2016).

[10] Titus P., Ganesamoorthy K. and

Balakrishnan P., The Detour Monophonic

Number of a Graph, J. Combin. Math.

Combin. Comput., 84, pp. 179-188, (2013).

[11] Titus P., Santhakumaran A.P. and

Ganesamoorthy K., The Connected Detour

Monophonic Number of a Graph, TWMS

Journal of Applied and Engineering

Mathematics, Vol. 6, No.1, pp. 75-86,

(2016).

[12] Johnwin Beaula N.E., Joseph Robin S., The

Outer Connected Detourmonophonic

Number of a Graph, RATIO

MATHEMATICA, Vol. 44, 2022.

[13] Ilin, Vladimir & Simic, Dragan, A review of

computational intelligence methods for

traffic management systems. Journal of Road

and Traffic Engineering. 67. 25-30.

10.31075/67.04.05, 2021.

[14] Jiawei Xue, Nan Jiang, Senwei Liang,

Qiyuan Pang, Takahiro Yabe, Satish V.

Ukkusuri & Jianzhu Ma, Quantifying the

spatial homogeneity of urban road networks

via graph neural networks., Nature Machine

Intelligence volume 4, pages246–257 (2022)

[15] Xiangyu Li; Bodong Shang; Caiguo Li;

Zhuhang Li., Coverage in Cooperative LEO

Satellite Networks, Journal of

Communication and Information Networks,

Vol. 8, Issue 4, pp.329-340 December 2023.

[16] Zalán Heszberger, AndrásGulyás, József

Bíró, Gábor Rétvári 1, Márton Novák, Attila

Kőrösi, Mariann Slíz The role of detours in

individual human navigation patterns of

complex networks, Scientific Reports, Vol.

10, 1098 (2020).

[17] Rawat, Khushi & Kapoor, Chirag & Goyal,

Himanshu & Sharma, Sachin.. Artificial

Intelligence Based Optimized Traffic

Diversion System in Smart Cities. Advanced

Communication and Intelligent Systems

(CCIS), Vol. 1921 pp. 97-108 (2023).

[18] T. Parsons and J. Seo, "FS-ACO: An

Algorithm for Unsafe U-Turn Detours in

Service Vehicle Route Optimization

Applications," 23rd International

Conference on Control, Automation and

Systems (ICCAS), Yeosu, Korea, Republic of,

2023, pp. 937-940, 2023. doi:

10.23919/ICCAS59377.2023.10316850.

[19] Maja Sareveska, Overview of RBF NN and

Antenna Systems, WSEAS Transactions On

Electronics, Vol. 13 pp. 84-88, 2022,

https://doi.org/10.37394/232017.2022.13.11.

[20] E.S. Ali, S.M. Abd Elasim, Optimal Sizing

and Locations of Capacitors using Slime

Model Algorithm, WSEAS Transactions on

Power Systems, Vol. 17, 38 pp.382-390,

(2022,

https://doi.org/10.37394/232016.2022.17.38.

[21] Zaid S. AI-Shamaain, Hussein. D. AI-Majali,

Bilal. H. AI-Majali, Out-of-Step Detection

based on Phasor Measurement Unit, WSEAS

Transactions on Power Systems, Vol. 18, 36

pp.354-363, 2023,

https://doi.org/10.37394/232016.2023.18.36.

Contribution of Individual Authors to the

Creation of a Scientific Article (Ghostwriting

Policy)

The authors equally contributed in the present

research, at all stages from the formulation of the

new parameter to the final results and their proofs.

Sources of Funding for Research Presented in a

Scientific Article or Scientific Article Itself

No funding was received for conducting this study.

Conflict of Interest

The authors have no conflicts of interest to declare.

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the

Creative Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en

_US

WSEAS TRANSACTIONS on COMPUTERS

DOI: 10.37394/23205.2024.23.5

M. Mahendran, R. Kavitha

E-ISSN: 2224-2872

Volume 23, 2024