# Strong Total Monophonic Problems in Product Graphs, Networks, and Its Computational Complexity

Authors: Eddith Sarah Varghese; D. Antony Xavier; Ammar Alsinai; Deepa Mathew; S. Arul Amirtha Raja; Hanan Ahmed
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG be a graph with vertex set as VG and edge set as EG which is simple as well as connected. The problem of strong total monophonic set is to find the set of vertices T⊆VG, which contains no isolated vertices, and all the vertices in VG\T lie on a fixed unique chordless path between the pair of vertices in T. The cardinality of strong total monophonic set which is minimum is defined as strong total monophonic number, denoted by smtG. We proved the NP-completeness of strong total monophonic set for general graphs. The strong total monophonic number of certain graphs and networks is derived. If l,m,n are positive integers with 5≤l≤m≤n and m≤2l−1, then we can construct a connected graph G with strong monophonic number l and strong total monophonic number m.


---

## Body

## 1. Introduction

Consider a simple connected graphGV,E with order m and size n. We refer [1] for the basic graph theoretical definitions. We denote i∈1,2,…,n as i∈n. Some of the variants for covering the vertices problem are referred in [2–19]. Some results on strong geodetic problems can be referred in [15–19]. A set S⊆VG is a geodetic set if it covers all the vertices of VG\S, and the cardinality of smallest geodetic set is called the geodetic number, denoted by gG. This concept is introduced by Harary et al. [3]. If S⊆V, then for each pair of vertices x,y∈S,x≠y, let g˜x,y be a selected fixed shortest x−y path. Then, we set I˜S=g˜x,y:x,y∈S}, and let VI˜S=∪P∈I˜SVP. If VI˜S=V, for some I˜S, then the set S is called a strong geodetic set, and the strong geodetic problem is to find a minimum strong geodetic set S of G [5].Ap−q monophonic path is a chordless p−q path. The monophonic distance is the number of edges of the chordless path, denoted by dmp,q. The monophonic eccentricity of a vertex p∈VG is the maximum monophonic distance between p and another vertex in G. The monophonic diameter, dm, and monophonic radius, rm, of G are the maximum and minimum monophonic eccentricity among the vertices in G, respectively. A set of vertices S⊆Vis defined as monophonic set (MS) if every vertex of G\S lies on a monophonic path joining some pair of vertices in S, and the cardinality of such smallest set is called monophonic number, denoted by mG. We refer [6–10] for other parameters of monophonic number. If every vertex of G\S lies on a unique fixed monophonic path between the pair of vertices in S⊆VG, then S is said to be a strong monophonic set (SMS, for short) which is defined in [11]. Its minimum cardinality is called strong monophonic number, denoted by smG.


## 2. Motivation

Graph theory plays a vital role in modelling our day to day activities into graphs. We can model the traffic system in a region using graphs where the vertices are junctions of roads. The police officers can be stationed in such a way that (i) two police officers are stationed at junctions adjacent so that they can support each other if they face any issue, and (ii) two police officers other than the former ones are stationed in such a way that they guard the junctions along the unique path than the former pair of police officers. Thus, we can assign minimum number of police officers as well as reduce the risk of traffic issues. For the above mentioned problem, the concept of strong total monophonic problem is helpful. This concept can also be useful in power supply station, water supply station, etc. The next section defines the problem, and its computational complexity and results are discussed in the following sections.


## 3. Strong Total Monophonic Number of a Graph

A total monophonic set (TMS, for short), S⊆VG, is a monophonic set whose induced subgraph does not contain any isolated vertices. The cardinality of minimum total monophonic set is called total monophonic number (TM, for short), denoted by mtG. A set T⊆VG is said to be a strong total monophonic set (STMS, for short) if T is a strong monophonic set, and the subgraph induced by T does not contain isolated vertices. The cardinality of such smallest STMS is called strong total monophonic number, smtG.In Figure1, the TMS is a,b,f,g and mtS=4. The STMS is a,b,c,d,e and smtS=5.Figure 1
GraphS with mtS=4 and smtS=5.We recall some terms and definitions required. Simplicial vertices of a graphG are those vertices whose neighbourhood induces a clique and is denoted by ExtG. The vertex adjacent to the vertex of degree 1, that is, end vertex is called stem vertex. The sets of all end vertices and all stems are denoted by ΩG and Ω1G, respectively [12].Proposition 1.
EveryΩG and Ω1G of a connected graph G belongs to every STMS of G. If the set of all ΩG and Ω1G forms a STMS, then it is the unique minimum strong total monophonic set of G.Corollary 1.
For complete graphKm,m≥2,smtKm=m.Theorem 1.
The set of allΩT and Ω1T is the unique minimum STMS for any nontrivial tree T.Proof.
Since extreme and stem vertices of a nontrivial treeT form a STMS of T, the result is obtained from Proposition 1.Result 1.
For pathPn,n≥4,smtPn=4.Result 2.
For star graphK1,n−1,smtK1,n−1=n.Theorem 2.
LetH be a connected graph of order m≥2, then(i)
2≤smH≤smtH≤m(ii)
smtH≤2smHProof.
(i)
A strong monophonic set,SMS, contains a minimum of 2 vertices or more; thus, smH≥2. Each STMS is a strong monophonic set; therefore, smH≤smtH. Since VH is a STMS of H, it is obvious that smtH≤m. Hence, 2≤smH≤smtH≤m.(ii)
LetT=u1,u2,…,un;n≤m be the strong monophonic set of H. Then, T∪yi;yi∈Nui;1≤i≤n is the STMS. Therefore, smtH≤2smH.SincesmP2=smtP2=2, the lower bound of Theorem 2 (i) is sharp. As smKn=smtKn=n, the upper bound of Theorem 2 (i) is sharp. Also for Pnn≥4,smPn=2 and smtPn=4. Therefore, the bound given by Theorem 2 (ii) is sharp.


## 4. Complexity Results

We are reducing the problem of strong total monophonic for general graphs from the decision problem, whether there exists an induced path between two vertices such that it passes through a third vertex. Using the above concept, we solve NP-completeness ofSTMS.Theorem 3.
(See [13]). Let x,y,z be three distinct vertices in a graph G. Deciding whether there is an induced path from x to y passing through z is NP-complete.Theorem 4.
TheSTM problem for general graphs is NP-complete.Proof.
Given a graphH with distinct vertices p,q,r and construct the graph H′ as follows: let p′,q′∈VH′ such that these vertices are adjacent to all the vertices in VHr. A pendant vertex a is joined to the vertex p′. Similarly, pendant vertices a1,a2,…,an−1 are joined to the vertex v, refer Figure 2. Let S=p′,q′,a,a1,a2,…,an−1 since the set of vertices of T forms a set of ExtH and stem vertices, which belong to any STMS of H′. Also, the monophonic paths between the vertices in T do not cover the vertex r. It is straightforward to see that every induced path in H is also an induced path in H′. The monophonic paths between x and x′ where x′∈S and x∈VH will not cover the vertex r. Consider A=T∪u,v:u,v∈VH. Clearly, u,v are nonextreme vertices in A. It is straightforward that A is a STMS in H′ if and only if the induced path between p and q contains r in H.Figure 2
Illustration of NP-completeness of general graph.


## 5. Results

Theorem 5.
LetH be a graph of order n with monophonic diameter dm, then smtH≥⌈2dm−2+4dm−22+8ndm−1/2dm−1⌉.Proof.
LetH be a connected graph with the strong total monophonic set S, and let S=s. No isolated vertices are contained in GS. If xy∈EGS,x,y∈S, then the monophonic path between x and y does not cover any vertices of V/S. Note that EGS≥s/2. For a,b∈S, the a−b fixed monophonic path covers atmost dm−1 vertices and n−s vertices are covered by atmost s2−s/2 monophonic paths. Thus, n−s≤s2−s/2dm−1. Therefore, we get smtH≥⌈2dm−2+4dm−12+8ndm−1/2dm−1⌉.The above bound is sharp for Figure3.Figure 3
A graphH with smtH≥⌈2dm−2+4dm−12+8ndm−1/2dm−1⌉.Theorem 6.
smtH=2 if and only if H≅K2.Proof.
IfH=K2, then smtH=2. Conversely, assume S=x,y be a minimum STMS of H. Suppose the length of x−y monophonic path is greater than 2, then it has an internal vertex. Let it be w, such that w∈VH\S. Therefore, GS has isolated vertices, which is a contradiction. Therefore, the only possibility is H≅K2.Theorem 7.
smtH=3 if and only if H≅Cn or P3.Proof.
Clearly, for pathP3,smtH=3.
LetH be cycle Cn:v1,v2,…,vn of order n. By Theorem 6, smtH≥3. Let S=v1,vn−1,vn. The set S is a strong monophonic set of Cn. Hence, smCn=3.
Conversely, letsmtH=3. Let us assume that H is not a path P3. Let S=a,b,c be a STMS of G. Since no isolated vertices are contained in GS, one of the vertex, say, c must be adjacent to both a and b. Therefore, only a−b fixed monophonic path which covers the vertices of H\S exists. Therefore, H≅Cn.Corollary 2.
IfH is not isomorphic to K2,P3, and Cn, then smtH≥4.Proof.
Proof follows from Theorems6 and 7.Theorem 8.
LetH be a connected graph of order m. If mtH=m−1, then smtH=m−1.Proof.
LetX be a total monophonic set of G. Let a∈VG\X. Then, there exists b,c∈X such that a lies on b−c monophonic path. Since it is the unique fixed path, X is the strong total monophonic set. Therefore, smtH=m−1.Converse of the theorem is not true. ForH=Kn−e,n≥5,smtH=n−1 but mtH=3.Sum of two graphsS and T is a graph with vertices VS+VT and edges ES+ET+uivj:ui∈VS,vj∈VT.Theorem 9.
LetS and T be two connected graphs. Let P∈VS+T and P∩VS≠ϕ,P∩VT≠ϕ. If P∩VS is a monophonic set of S or P∩VT is a monophonic set of T, then P is a total monophonic set of S+T.Proof.
LetX=P∩VS is a MS of S. If X=VS, then obviously P is a TMS of S+T. Let X≠VS. Let u∈VS\X. Then, there exists a,b∈X such that c lies in the a−b monophonic path of S. Obviously, every monophonic path in S is a monophonic path of S+T. Since dS+Ta,b=2, all the vertices in T lie in the r−s monophonic path, where r,s∈X. Therefore, X is a MS of S+T. Since U∩VT≠ϕ, U is a TMS of S+T.But Theorem9 is not applicable to a strong total monophonic number of G+H. Consider P3+P4, as in Figure 4, the total monophonic set S contains a,c,d where a,c is the monophonic set of P3 and S∩P4=d whereas the strong total monophonic set is a,c,d,g.Figure 4
mtP3+P4=3 and smtP3+P4=4.Theorem 10.
LetS and T be two noncomplete graphs, then mtS+T≤minmS+1,mT+1,4.Proof.
LetB=mS be the minimum MS of S and x∈T. Then, by Theorem 9, B∪x is a TMS of S+T. Thus, mtS+T≤mS+1. The proof is similar for mtS+T≤mT+1. By taking two vertices in S and two vertices in T, a total monophonic set of S+T can be formed. Hence, mtS+T≤4. Therefore, mtS+T≤minmS+1,mT+1,4.Theorem 11.
LetS and T be two graphs, then smtS+T≤smS+smT.Proof.
LetZ and Z′ be the SMS of S and T, respectively. Clearly, Z∪Z′ is a strong monophonic set of S+T. Also GZ∪Z′ contains no isolated vertices. Hence, smtG+H≤smG+smH.The bound is sharp forPn+Cm.The corona product of two graphsS and T, S°T, is the graph obtained by joining every vertex of kth copy of T to kth vertex of S.Theorem 12.
LetX and X′ be two connected graphs, then smtX°X′≤nX1+smX′.Proof.
LetoX=n,oX′=m. X°X′ contains n copies of X′, that is, X1′,X2′,…,Xn′. Let S=h1,h2,…,hk be a SMS of X′. Then, Si=h1i,h2i,…,hni is a SMS of Xi′,i∈n. It is straightforward to see VX∪i=1nSi is a STMS of X°X′. Therefore, smtX°X′≤nX1+smX′.The sharpness for the above bound is obtained forPn°Pm,n,m≥3.Cartesian product of two graphsS and T, S□T is a graph with vertex set VS×VT, and two vertices s,t and s′,t′ are adjacent in S□T if and only if s=s′ and t is adjacent to t′ or t=t′ and s is adjacent to s′.Theorem 13.
(See [11]). Let G and H be connected graphs with smG=p and smH=q,2≤p,q. Then, smG□H≤pq−1 and the bound are sharp.Remark 1.
By Theorem13, any three corner vertices of Pn□Pm are a strong monophonic set.Theorem 14.
LetS and T be graphs with smS=m and smT=n,m,n≥2. Then, smtS□T≤2mn−1.Proof.
By Theorem13, smS□T≤mn−1. By Theorem 2, smtS□T≤2mn−1.Theorem 15.
LetS and T be two connected graphs. Then, smtS□T≤minsmSsmtT,smtSsmT.Proof.
LetVS□T=xi,yj:xi∈VS,i∈VS,yi∈VT,j∈VT. Let smS=l and smtT=l′. Let X=x1,x2,…,xl be the SMS of G and Y=y1,y2,…,yl′ be the STMS of H. Let x,y∈VS□T\X×Y. Then, there exists a fixed monophonic path P:li,lj where li,lj∈X such that x lies on Pi path. Similarly, y lies on a fixed monophonic path Q:li′,lj′ where li′,lj′∈Y. By Remark 1, x,y will lie on some fixed monophonic path with adjacent edges P and Q and corner vertices li,li′,li,lj′,lj,li′,lj,lj′. Since Y is a strong total monophonic set, GX×Y contains no isolated vertices. Hence, smtS□T≤ll′. By symmetry, smtS□T≤smtSsmT.
Therefore,smtS□T≤minsmSsmtT,smtSsmT.The bound is sharp forPn□P2.Strong product of two graphsS and T,S⊠T, is a graph with vertex set VS×VT, and two vertices s,t and s′,t′ are adjacent in S⊠T if and only if s=s′ and t is adjacent to t′ or t=t′ and s is adjacent to s′ or t is adjacent to t′ and s is adjacent to s′.Theorem 16.
For two connected graphsS and T, smtS⊠T≤minsmSsmtT,smtSsmT.The proof is similar to Theorem15.Sharpness of the bound is obtained forPn⊠P2.Theorem 17.
smtPn⊠Pm≤8, where n,m≥4.Proof.
Let the vertices ofPn⊠Pm be ai,bj:1≤i≤m;1≤j≤n. By Theorem 7, smtG≥4. Denote S=a1,b1,a1,bn,am,b1,am,bn. All the internal and external vertices are covered by a unique fixed chordless path between the pair of vertices in S. Thus, all the vertices in Pn⊠Pm lie on some unique fixed monophonic path. Since GS contains isolated vertices, at most one vertex adjacent to each vertex in the set S is also considered along with S to form the strong total monophonic number. Thus, smtPn⊠Pm≤8.Theorem 18.
For Petersen graph,smtP5,2=4.Proof.
By Corollary2, smtG≥4. Consider the set S⊆VG such that S=x,y,z,w and x is adjacent to y and z is adjacent to w. The vertices are covered by unique fixed x−w, z−w, and z−y monophonic paths as given in Figure 5. Thus, S is a STMS, and smtG=4.Figure 5
Petersen graphG with smtG=4.Theorem 19.
The strong total monophonic number of the Sirpenski graphSn,k of dimension, n≥2, is 6.Proof.
In the Sierpinski graph, the corner vertices form simplicial vertices. Also,ExtSn,k∈STMS. The ExtSn,k covers all the vertices in a unique fixed monophonic path. Thus, ExtSn,k=3. By definition of a strong total monophonic number, the set must consist of no isolated vertices; therefore, the strong total monophonic number of the Sierpinski graph is 6, that is, twice the number of simplicial vertices.Theorem 20.
Forn-dimensional silicate network SLn, smtSLn=6n2+6n+nn−1/2.Proof.
LetS be STMS. By Proposition 1, ExtSLn∈STMS. The number of simplicial vertices in SLn=6n2+6n since S should not contain isolated vertices. The minimum number of vertices required for S to be not isolated is nn−1/2. Therefore, smtG=6n2+6n+nn−1/2.Theorem 21.
For wheel graphWn on n≥5 vertices, smtWn=4.Proof.
By Corollary2, smtWn≥4. Let Wn=Cn−1+K1 be the wheel graph of order n,n≥5 which is constructed as follows. Let u0 be center vertex which is adjacent to all vertices of Cn−1,n≥5 and the diameter of wheel graph is 2, for all n≥5. The vertices that lie on the circle are denoted by u1,u2,…,un−1. The u1−un−2 unique fixed monophonic path covers all vertices except u0,un−1. Thus, the set u0,u1,un−2,un−1 forms the strong total monophonic set. Thus, smtWn=4.Result 3.
For a circulant graphC, smtC=4.Theorem 22.
For gridGn,m,smtGn,m=4.Proof.
By Corollary2, smtGn,m≥4. Assume rj,sk;1≤j≤n,1≤k≤m be the set of vertices of Gn,m. Let S=r1,s1,r2,s1,rn−1,sm,rn,sm. Without loss of generality, assume that n≤m.Case 1: whenn≅0mod4Except the last odd column, all the vertices in the odd columns are covered by ther1,s1−rn−1,sm unique fixed monophonic path (mp, for short). The mp is as follows: r1,s1−r1,sm,r2,sm,r3,sm−r3,s1,…,rn−3,s1−rn−3,sm−rn−1,sm. The unique fixed r2,s1−rn,smmp covers all the vertices in the even columns except the last even column, and the mp is as follows: r2,s1−r2,sm,r3,sm,r4,sm−r4,s1,…,rn−2,s1−rn−2,sm,rn−1,sm,rn,sm. The last odd column is covered by the unique fixed r2,s1−rn−1,smmp. The last even column is covered by r1,s1−rn,sm fixed mp. Thus, all vertices are covered by the set S. Therefore, smtGn,m=4.Case 2: whenn≅1mod4All the vertices in the odd columns lie on ther1,s1−rn−1,sm unique fixed mp. The mp is as follows: r1,s1−r1,sm,r2,sm,r3,sm−r3,s1,…,rn−3,sm−rn−3,s1−rn−1,s1−rn−1,sm−1. The unique fixed r2,s1−rn,smmp covers all the vertices in the even columns, and the mp is as follows: r2,s1−r2,sm,r3,sm,r4,sm−r4,s1,…,rn−2,s1−rn,s1−rn,sm.Case 3: whenn≅2mod4It is similar ton≅1mod4.Case 4: whenn≅3mod4All the vertices in the odd columns except the last odd column are covered by ther1,s1−rn−1,sm unique fixed mp. The mp is as follows: r1,s1−r1,sm,r2,sm,r3,sm−r3,s1,…,rn−2,s1−rn−2,sm,rn−1,sm. The unique fixed r2,s1−rn,smmp covers all the vertices in the even columns, and the mp is as follows: r2,s1−r2,sm,r3,sm,r4,sm−r4,s1,…,rn−1,s1−rn−1,sm,rn,sm. The last odd column lies on the unique fixed r2,s21−rn−1,smmp. The last even column is covered by r1,s1−rn,sm fixed mp. Thus, all vertices are covered by the set S. Therefore, smtGn,m=4.Theorem 23.
For cylinderPm□Cn,smtPm□Cn=4.Proof.
By Corollary2, smtPm□Cn≥4. Assume rj,sk;1≤j≤n,1≤k≤m be the set of vertices of Pn□Cm. Let T=r1,s1,rn,s1,rn−1,sm,rn,sm.Case 1: whenm≅0mod4All the vertices in the odd column except the last row are covered by unique fixedr1,s1−rn,smmp as follows: r1,s1−rn−1,s1,rn−1,s2,rn−1,s3−r1,s3,…,rn−1,sm−1−r1,sm−1,r1,sm,rn,sm. All vertices in the even columns except the last even column and last row are covered by r1,s1−rn−1,smmp where the path is as follows: r1,s1,r1,s2−rn−1,s2,…,r1,sm−2−rn−1,sm−2,rn−1,sm−1,rn−1,sm. A unique fixed rn,s1−rn,smmp covers all vertices that lie on the last row. The vertices r1,sm−rn−2,sm lie on the rn,s1−rn−1,sm fixed mp. Thus, all the vertices are covered by the set T. Therefore, smtPm□Cn=4.Case 2: whenm≅1mod4All the vertices in the odd columns except the last row are covered by a unique fixedr1,s1−rn−1,smmp as follows: r1,s1−rn−1,s1,rn−1,s2,rn−1,s3−r1,s3,…,r1,sm−rn−1,sm. All vertices in the even columns except the last row are covered by r1,s1−rn,sm where the path is as follows: r1,s1,r1,s2−rn−1,s2,…,rn−1,sm−1−r1,sm−1,r1,sm,rn,sm. A fixed rn,s1−rn,smmp covers all vertices that lie on the last row. Since all the vertices are covered by the set T,smtPm□Cn=4.Case 3: whenm≅2mod4The vertices in the odd columns except the last row are covered by the unique fixedr1,s1−rn,smmp as follows: r1,s1−rn−1,s1,rn−1,s2,rn−1,s3−r1,s3,…,r1,sm−1−rn−1,sm−1,rn−1,sm,rn,sm. All vertices in the even columns except the last row are covered by r1,s1−rn−1,sm where the path is as follows: r1,s1,r1,s2−rn−1,s2,…,rn−1,sm−2−r1,sm−2,r1,sm−1,r1,sm,rn,sm. A fixed rn,s1−rn,smmp covers all vertices that lie on the last row. Thus, all the vertices in Pn□Cm are covered by the set T. Hence, smtPn□Cm=4.Case 4: whenm≅3mod4The vertices in the odd columns with an exception for last column and last row are covered byr1,s1−rn,sm unique fixed mp. All the vertices in the even columns are covered by r1,s1−rn−1,sm unique fixed mp. All the vertices in the last row are covered by rn,s1−rn,sm unique fixed mp. The vertices r1,sm−rn−1,sm are covered by unique fixed rn,s1−rn−1,smmp. Thus, the vertices are covered by the set T; therefore, smtPn□Cm=4.Theorem 24.
For torus graph, the strong total monophonic number is 4.The proof is similar to Theorem23. Thus, we omit the proof.Theorem 25.
For two positive integersl,m where 5≤l≤m≤n and m≤2l−1, there exists a connected graph S of order n with smS=l and smtS=m.Proof.
Case 1: ifl<m≤n. Consider a path Pn−m+2:v1,v2,…,vn−m+3 of order n−m+3. Join a vertex u to the vertices v1 and v2. Join m−l−1 copies of path P2:uiui′;1≤i≤m−l−1 and 2m−l−1 vertices w1,w2,…,w2m−l−1 to the vertex vn−l+3, refer to Figure 6.LetU1=ui:1≤i≤m−l−1∪wj:1≤j≤2m−l−1 denote the set of simplicial vertices. Let U2=ui′;1≤i≤m−l−1∪vn−m+3 be the set of stem vertices. Then, U1∪u,v1 is a strong monophonic set, and U1∪u,v1∪U2 is a strong total monophonic set of S. Therefore, smS=l,smtS=m.Case 2: ifl=m<n. Consider a path Pn−l+1:v1,v2,…,vn−l+1. Let S be the graph of order n obtained by joining wi,1≤i≤l−3 to the vertices v1 and v2 and joining each vertex of P2:u1,u2 to the vertex vn−l+1, refer to Figure 7.The setv1,u1,u2∪wi;1≤i≤l−3 is the strong monophonic and strong total monophonic set of S.Case 3: Ifl=m=n. When G=Kn, then smS=smtS=n.Figure 6
A graph withsmG=a,smtG=b for a<b≤n.Figure 7
A graph withsmG=a,smtG=b for a=b<n.Theorem 26.
For three positive integersradS,diamS,l where radS≤diamS≤2radS<n and l≥d+1, there exists a connected graph G=KnG with radiusG=r,diameterG=d, and smtG=l.Proof.
Ifr=1,d=1, then G=Kn.
Ifr=1,d=2, then G=K1,n−1.
Consider a cycleC2r:u1,u2,…,u2r. The graph G is constructed by joining path Pd−r:v1,v2,…,vd−r to the vertex u2r and joining the isolated vertices w1,w2,…wl−4 to the vertex vd−r−1, refer to Figure 8. The set u2,u3,vd−r−1,vd−r,w1,w2,…,wl−4 forms the STMS. Thus, smtG=l.Figure 8
A graph with radiusr, diameter d, and smtG=l.



---

*Source: 6194734-2022-09-08.xml*