# Bounds on Co-Independent Liar’s Domination in Graphs

Authors: K. Suriya Prabha; S. Amutha; N. Anbazhagan; Ismail Naci Cangul
Journal: Journal of Mathematics
 (2021)

---

## Abstract

A setS⊆V of a graph G=V,E is called a co-independent liar’s dominating set of G if (i) for all v∈V, NGv∩S≥2, (ii) for every pair u,v∈V of distinct vertices, NGu∪NGv∩S≥3, and (iii) the induced subgraph of G on V−S has no edge. The minimum cardinality of vertices in such a set is called the co-independent liar’s domination number of G, and it is denoted by γcoiLRG. In this paper, we introduce the concept of co-independent liar’s domination number of the middle graph of some standard graphs such as path and cycle graphs, and we propose some bounds on this new parameter.


---

## Body

## 1. Introduction

For notations and nomenclature, we refer [1]. Specifically, let G=V,E be a graph with vertex set V of order p=V and edge set E of size q=E. The diameter of G is the greatest distance between any two vertices of G. The middle graph MG is the derived graph obtained from G by inserting a new vertex into every edge of G and then joining these new vertices by edges which lie on the adjacent edges of G [2]. Haynes et al. introduced the concept of domination in graphs [3].A topological index is a real number related to a graph, which must be a structural invariant. The topological indices are a vital tool for quantitative structure activity relationship and quantitative structure property relationship. For more work on topological indices of a graph, refer recent papers [4, 5].The concept of liar’s domination was introduced by Panda and Paul in [6]. A graph G=V,E admits a liar’s dominating set if each of its connected components has at least three vertices. Several different domination parameters were studied in [7–12]. For references on liar’s domination, see, for instance, [2, 13]. A subset S⊆V of a graph G=V,E is called a co-independent liar’s dominating set of G if (i) for all v∈V, NGv∩S≥2, (ii) for every pair u,v∈V of distinct vertices, NGu∪NGv∩S≥3, and (iii) the induced subgraph of G on V−S has no edge. The minimum cardinality of vertices in such a set is called the co-independent liar’s domination number of G, and it is denoted by γcoiLRG. In this paper, we initiate the study of co-independent liar’s domination in graphs.


## 2. Co-Independent Liar’s Domination in Graphs

In this section, we first strengthen the co-independent liar’s domination number of the middle graphs of some standard graphs. Eventually, some bounds will be obtained.Theorem 1.
LetMPp be the middle graph of a path graph Pp of order p. Then,(1)γcoiLRMPp≤p+1.Proof.
Letu1,u2,u3,…,up be the vertices of Pp and also the vertices in VMPp−Pp be up+1,up+2,up+3,…,u2p−1. Let u∈VMPp. We prove that all the vertices of MPp get a co-independent liars dominating set arising in four cases:(1)
Case (i): letu=u1. Recall that degu1=degup=1. So, Nu1=u1,up+1 in MPp and Nu1=2. Therefore, Nu∩S≥2, for all u∈VMPp, and every set consisting of a vertex of Nu1 should be a component of S and u1,up+1∈S. So, u2p−1,up∈S for u=up. Therefore, u1,up+1,u2p−1,up∈S. Hence, u2∈V−S, and it is independent.(2)
Case (ii): letu be an element of u2,u3,u4,…,up−1. Then, degu2=degu3=⋯=degup−1=2 and Nui=ui,up+i,up+i−1 for i=2,3,…,p−1. Let Nuj∩Nuk=Sj,k for k=2,3,…,p−2 and j=k+1. Then,(2)∪j,k=2p−1Sj,k=up+2,up+3,up+4,…,u2p−2∈S.Therefore,u1,up+1,up+2,up+3,up+4,…,u2p−2,u2p−1,up∈S, and also, we get Nuj∩S≥2 for all uj,j=1,2,3,…,p. Next, we demonstrate that Nu∪Nv∩S≥3 for every pair of distinct vertices. Note that Nuj∩S=2, Nuk∩S≥3, and Nuj∩Nuk≤1. So, we have Nuj∪Nuk∩S≥3 for j,k=1,2,…,p. Therefore, u2,u3,u4,…,up−1∈V−S, and no two elements are adjacent in V−S.(3)
Case (iii): letu=up+1. Then, degup+1=3, and we can write Nup+1=u1,u2,up+1,up+2. We have Nup+1∩S=u1,up+1,up+2, and therefore, Nup+1∩S=3. Let u=u2p−1. Then, degu2p−1=3 and Nu2p−1=u2p−1,up−1,up,u2p−2. We get Nu2p−1∩S=u2p−2,u2p−1,up and similarly Nu2p−1∩S=3.(4)
Case (iv): letu be an element of up+2,up+3,…,u2p−2 and degup+2=degup+3=⋯=degu2p−2=4. Then,(3)Nup+2=up+2,up+1,u2,u3,up+3,Nup+3=up+3,up+2,u3,u4,up+4,⋅⋅⋅Nu2p−2=u2p−2,u2p−3,up−2,up−1,u2p−1,and we obtain Nuj∩S≥3 for j=p+2,p+3,…,2p−2. Therefore, u2,u3,u4,…,up−1∈V−S, and for all uv∈V−S, uv∉E. Hence, S=u1,up+1,up+2,up+3,…,u2p−2,u2p−1,up is a co-independent liar’s dominating set of MPp and γcoiLRMPp≤p+1.Theorem 2.
LetMCp be the middle graph of a cycle graph. Then,(4)γcoiLRMCp≤p.Proof.
Let the vertices ofCp be u1,u2,…,up and up+1,up+2,…,u2p be the vertices of VMCp−Cp. We investigate all vertices of MCp to get a co-independent liar’s dominating set in two cases:(1)
Case (i): letdegui=2 where i=1,2,3,…,p, and let u be an element of u1,u2,…,up. Then, S contains at least two vertices of Nui and it double dominates ui for i=1,2,3,…,p. Hence,(5)Nu1=u1,up+1,up+2,Nu2=u2,up+2,up+3,⋅⋅⋅Nup−1=up−1,u2p−1,u2p,Nup=up,u2p,up+1.Ifuv∈ECp, then we consider Nu∩Nv. Let Nuj∩Nuk=Sj,k, where j,k=1,2,3,…,p. So, we have(6)S1=∪j,k=1pSj,k=up+1,up+2,…,u2p−2,u2p−1,u2p∈S.Therefore,S1 double dominates ui for i=1,2,…,p. Clearly, we have Nuj∪Nuk∩S1≥3 as Nuj∩S1=2 and Nuj∩Nuk=1 for the vertices uj and uk, where ujuk∈ECp for j,k=1,2,…,p. Likewise, we have Nuj∪Nuk∩S1=4≥3 as Nuj∩S1=2 and Nuj∩Nuk=0 for the vertices uj and uk, where ujuk∉ECp for j,k=1,2,3,…,p. Therefore, S1 triple dominates ui for i=1,2,3,…,p. Hence, u1,u2,…,up∈V−S, and no two elements in V−S can form an edge.(2)
Case (ii): letdeguj=4, where j=p+1,p+2,…,2p, and let u be an element of up+1,…,u2p.(7)Nup+1=up+1,up,u1,u2p,up+2,Nup+2=up+2,u1,u2,up+1,up+3,⋅⋅⋅Nu2p−1=u2p−1,up−2,up−1,u2p−2,u2p,Nu2p=u2p,up−1,up,u2p−1,up+1.
We obtainNuj∩S1=3 for j=p+1,p+2,…,2p. Therefore, S1 triple dominates uj for j=p+1,p+2,…,2p. So, u1,u2,…,up∈V−S. For every u,v∈V−S, uv∉E. Hence, S=S1=up+1,up+2,…,u2p is a co-independent liar’s dominating set of MCp and γcoiLRMCp≤p.Note 1.
LetMWp be the middle graph of a wheel graph, then a co-independent liar’s dominating set does not exist.We have the following lower bound on co-independent liar’s domination number in terms of the diameter of a graph.Theorem 3.
LetG be a graph of order p≥4. Then,(8)γcoiLRG≥34diamG+2.Proof.
LetS be a γcoiLRG set. We employ an induction on the number r of components of GS to indicate that γcoiLRG≥diamG−r+2, and hence the result will follow: suppose that GS has precisely one component, that is, GS is connected and S≥3. We show that the distance between any pair of vertices in G is atmost S−1. Let y1 and y2 be two distinct vertices of G. If y1,y2∈S, then dGy1,y2≤diamGS≤S−1. Next, assume that y1∉S and y2∉S. It may be verified that Ny1∩S≥2. Since y1∉S, there are at least two vertices yi and yj in Ny1∩S. Similarly, it may be concluded that there are two vertices yi′ and yj′ in Ny2∩S. If yi,yj∩yi′,yj′≠ϕ, then dy1,y2≤S−1 since S≥3. Suppose that yi,yj∩yi′,yj′=ϕ. Assume, without loss of generality, that dGSyi,yi′=mindGSv,w:v∈yi,yj,w∈yi′,yj′. It is easy to verify that dGSyi,yi′≤S−3. Now,(9)dGy1,y2≤dGy1,yi+dGSyi,yi′+dGyi′,y2≤1+S−3+1=S−1.
Next, we takey1∉S and y2∈S. As before, there are two vertices yi and yj in Ny1∩S. If yi,yj∩y2≠ϕ, then dGy1,y2=1≤S−1 as S≥3. Let yi,yj∩y2=ϕ. Without loss of generality, we might assume that dGSyi,y2=mindGSv,y2:v∈yi,yj. Then, dGy1,y2≤dGy1,yi+dGSyi,y2≤1+S−2=S−1. Suppose that the result is true for the number of components of GS which are less than r. Let S=∪i=1rSi, where GSi is the component of GS for i=1,2,3,…,r. Let Vi be the set of all vertices of VG−S with at least two neighbors in Li and Gi=GVi∪Si. If for every m,n∈V−S, then mn∉EG. In order to maximize the diameter, without loss of generality, we may assume that, for i=1,2,…,r−1, NGi∩NGi+1=1 and for every j>i+1, NGi∩NGj=0. Let NGi∩NGi+1=vi for i=1,2,…,r−1. Let p,q be two distinct vertices of VG with dGp,q=diamG. Then,(10)dGp,q≤∑i=1rdiamGi+dGG1,v1+dGv1,G2+dGG2,v2+⋯+dGvr−1,Gr=∑i=1rdiamGi+2r−1.
By induction, we find thatdiamGi≤Si−1,∀1≤i≤r. Hence,(11)dGp,q≤∑i=1rSi−1+2r−1.
Hence,dGp,q≤S+r−2. Therefore, γcoiLRG≥diamG−r+2.
We now study some bounds on co-independent liar’s domination number in terms of the components of a cut vertex deleted graph.Theorem 4.
Letx be a cut vertex of a graph G and T1,T2,T3,…,Tm be the components of G−x. If Tj≥2 and Gj=Tj∪x for 1≤j≤m, then(12)∑j=1mγcoiLRGj−2m−1≤γcoiLRG≤∑j=1mγcoiLRGj.Proof.
First, we show that∑j=1mγcoiLRGj−2m−1≤γcoiLRG. Let S be a γcoiLRG set and Sj=S∩VGj for j=1,2,3,…,m. If x∈S, we have ∑j=1mSj=γcoiLRG+m and if x∉S, then ∑j=1mSj=γcoiLRG. Clearly, for every vertex, u∈VGj/x, j=1,2,3,…,m, NGju∩Sj=NGu∩S, and NGju∩Sj≥2. Moreover, for any pair u,v∈VGj/x, j=1,2,3,…,m, Nu∪Nv∩Sj=Nu∪Nv∩S≥3, and also the set VGj−Sj is independent. We have to consider following two cases:Case (i): letx∈S. For any 1≤j≤m, there is at least one vertex rj∈Nx∩Sj, so Nx∩Sj≥2. Since each vertex z∈VGj/NGjx∩Nrj should be double dominated by Sj, there is at least a vertex w∈Nz∩Sj, w≠rj. Therefore, for each vertex z∈VGj−NGjx∩Nrj,(13)NGjx∪Nz∩Sj≥x,rj,w=3.Hence, lety∈NGjx∩Nrj and Sj′=Sj∪z. So, for every vertex y∈NGjx∩Nrj,(14)NGjx∪Ny∩Sj′≥x,rj,z=3.and for everyr,s∈VGj−Sj, rs∉EGj. Hence, Sj′ is a co-independent liar’s dominating set for each Gj, and therefore,(15)γcoiLRGj≤Sj′=Sj+1.For each vertext∈Nx∩VGj, t∉Sj. Repeating these, each vertex z∈VGj/x should be double dominated by Sj. In such a component, there is at least one vertex z′∈Nz∩Sj. Let Sj′=Sj∪t for each vertex t∈Nx∩VGj, t∉Sj. Hence, for every vertex z∈VGj/x,(16)NGjx∪Nz∩Sj′≥x,t,z′=3.Also,(17)NGjx∩Sj′≥x,t=2.and no two vertices can be adjacent inVGj−Sj. There is at least one vertex rj∈Nx∩Sj. As before, for z∈VGj/NGjx∩Nrj, we have(18)NGjx∪Nz∩Sj≥x,rj,w=3.LetSj′=Sj∪z. For each vertex y∈NGjx∩Nrj, we have(19)NGjx∪Ny∩Sj′≥x,rj,z=3.Thus, for each pair of vertices inVGj−Sj for j=1,2,3,…,m, Sj′ is a co-independent liar’s dominating set and(20)γcoiLRG≤Sj′=Sj+1.Thus, in any case, asx∈S, S′ is a co-independent liar’s dominating set for Gj1≤j≤m. Thus,(21)∑j=1mγcoiLRGj≤∑j=1mSj′≤∑j=1mSj+1=∑j=1mSj+m=γcoiLRG+m−1+m.So,∑j=1mγcoiLRGj−2m−1≤γcoiLRG.Case (ii): letx∉S. Because Nx∩S≥2, there is at least one component. Without loss of generality, we might assume that r1∈Nx∩S1. Let Sj′=Sj∪x,rj, where rj is an arbitrary vertex in Nx∩VGj,j=1,2,3,…,m. As for every vertex z∈VGj/x, Nz∩Sj≥2, there are at least two vertices w,y∈Nz∩Sj. So, for each z∈VGj/x, we have(22)Nz∪NGjx∩Sj′≥w,y,x=3,and Nx∩Sj′≥x,rj=2, and for every r,s∈VGj−Sj, rs∉EGj. Therefore,(23)∑j=1mγcoiLRGj≤∑j=1mSj′≤∑j=1mSj+2−1=∑j=1mSj+2m−1=γcoiLRG+2m−1.
Similarly, the second inequality can be proven.
We now characterize the graphs according to the sensitivity of a co-independent liar’s dominating set versus a cut edge.Theorem 5.
Lete=xy be a cut edge (bridge) in a graph G and G1 and G2 be the components of G−e. If VG1≥4 and VG2≥4, then(24)γcoiLRG1+γcoiLRG2−2≤γcoiLRG≤γcoiLRG1+γcoiLRG2.Proof.
LetS be a co-independent liar’s dominating set and S1=S∩G1, S2=S∩G2. When x,y∉S, deleting the edge xy does not change the sizes of co-independent liar’s dominating sets of G1 and G2. Assume that x∈S and y∉S. Then, clearly, for every component of S having a minimum of four vertices, we can assume that there are two vertices x′∈Nx∩S1 and x″∈Nx∩S1∪Nx′∩S1/x,x′ and VG1−S1 has no edge. Similarly, there are two vertices y′∈Ny∩S2, y″∈Ny∩S2∪Ny′∩S2/y,y′, and also, the subgraph induced by VG2−S2 is independent. Let S1′=S1 and S2′=S2∪y. Then, S1′ and S2′ form co-independent liar’s dominating sets for G1 and G2 andS1′+S2′−1≤S.(25)S1′+S2′−1≤S.
Next, suppose that bothx and y∈S. Then, there is a vertex x′∈Nx∩S1 or y′∈Ny∩S2. Without loss of generality, we might assume that it is x′. Let S1′=S1∪x″, where x″∈Nx∩G1∪Nx′∩G1/x,x′ and S2′=S2∪y′,y″, where y′∈Ny∩G2 and y″∈Ny∩G2∪Ny′∩G2/y,y′. Therefore, S1′,S2′ form co-independent liar’s dominating sets of G1 and G2 and(26)S1′+S2′−2≤S.
The right side inequality follows from the fact that the union of theγcoiLRG1 set and the γcoiLRG2 set forms a co-independent liar’s dominating set for G.Theorem 6.
LetG and G¯ be connected and VG=p, p≥5, then 16≤γcoi_lrGγcoi_lrG¯≤p2.Proof.
The upper bound is obvious. We established the lower bound. LetG be a connected graph of order p such that G¯ is connected. Clearly, γcoi_lrG≥3 and γcoi_lrG¯≥3. The result is obvious if minγcoi_lrG,γcoi_lrG¯≥4. Hence, let minγcoi_lrG,γcoi_lrG¯=4. Without loss of generality, assume that γcoi_lrG=4. We show that γcoi_lrG¯≥4. Let S=u1,u2,u3,u4 be a γcoi_lrG set and S′ be a γcoi_lrG¯ set. We partition the set VG/S into two sets M=y∈VG/S:Ny∩S=3 and N=y∈VG/S:Ny∩S=4. Note that M=4. Since G¯ is connected and none of the vertices in N are adjacent to any vertex in S in G¯, we can deduce that M≥4. Hence, M=4. Let M=v1,v2,v3,v4, where vj is not adjacent uj in G for j=1,2,3,4. Since GS is connected, we may think that u1,u3⊆Nu2. Now, the only vertex adjacent to u2 in G¯ is v2, so v2,u2∈S′. In addition, according to the co-independent liar’s domination which has been discussed, u1,v1,u3,v3∩S′≥3. Therefore, γcoi_lrG¯=S′≥4.Theorem 7.
LetMT be the middle graph of a tree with p≥3. Then, γcoi_lrMT≤p+2.Proof.
Let the vertices ofT be u1,u2,u3,…,up and up+1,up+2,up+3,…,u2p−1 be the vertices of VMT. We prove that all vertices of MT arise in four cases to get a co-independent liars dominating set:(i)
Case (i): ifdegui=1, that is, ui is a pendant vertex in VMT, then Nui=ui,up+i in MT and Nui=2. Therefore, Nui∩S≥2, ∀ui∈VMT, and all the vertices of Nui should be components of S, ui,up+i∈S. So, u2p−1,up∈S for u=up. Therefore, ui,up+i,u2p−i,up∈S.(ii)
Case (ii): ifdegui=2 in VMT, then Nui=ui,up+i,up+i−1 for i=2,3,…,p−1. Let Nuj∩Nuk=Sj,k, where k=2,3,…,p−2 and j=k+1. Then, ∪j,k=2p−1Sj,k=up+2,up+3,up+4,…,u2p−2∈S. Therefore, u1,up+1,up+2,up+3,up+4,…,u2p−2,u2p−1,up∈S and Nuj∩S≥2,∀uj,j=1,2,3,…,p. Next, we demonstrate that Nu∪Nv∩S≥3 for every pair of distinct vertices. We see that Nuj∩S=2, Nuk∩S≥3, and Nuj∩Nuk≤1. So, we have Nuj∪Nuk∩S≥3, where j,k=1,2,…,p. Therefore, u2,u3,u4,…,up−1∈V−S, and no two elements are adjacent in V−S.(iii)
Case (iii): ifdegui=3 in VMT, then Nup+i=u1,u2,up+i,up+i+1. We have Nup+i∩S=u1,up+i,up+i+1 and Nup+i∩S=3. Let u be u2p−1. Then, degu2p−1=3 and Nu2p−1=u2p−1,up−1,up,u2p−2. We get Nu2p−1∩S=u2p−2,u2p−1,up and Nu2p−1∩S=3.(iv)
Case (iv): ifdegui=4 in VMT, then(27)Nup+2=up+2,up+1,u2,u3,up+3,Nup+3=up+3,up+2,u3,u4,up+4,⋅⋅⋅Nu2p−2=u2p−2,u2p−3,up−2,up−1,u2p−1.
We obtainNuj∩S≥3, where j=p+2,p+3,…,2p−2. Therefore, u2,u3,u4,…,up−1∈V−S, and for all uv∈V−S, uv∉E. Hence, S=u1,up+1,up+2,up+3,…,u2p−2,u2p−1,up is the co-independent liar’s dominating set of MT and γcoi_lrMT≤p+2.Remark 1.
(i) A tree is a co-independent liar’s dominating set. Indeed in Figure1(a), let VG=v1,v2,v3,v4,v5,v6,v7. If we take S=v1,v2,v3,v5,v6,v7, then V−S=v4 which is a co-independent liar’s dominating set. (ii) Co-independent liar’s dominating set need not exist for all trees. For example, in Figure 1(b), let VG=v1,v2,v3,v4,v5,v6. Suppose we take the co-independent liar’s dominating set S=v1,v2,v3,v4,v5,v6. But V−S=ϕ which satisfies conditions (i) and (ii) but not (iii).(i)
For allv∈V, NGv∩S≥2(ii)
For every pairu,v∈V of distinct vertices, NGu∪NGv∩S≥3(iii)
The induced subgraph ofG on V−S has no edgeFigure 1
Trees for Remark 1.
(a)(b)


## 3. Conclusion

In this paper, the co-independent liar’s domination number of the middle graphs of some graph classes such as path and cycle graphs is calculated. Also, some general results and bounds on the co-independent liar’s domination number of graphs are obtained. It has been shown that no general result can be obtained for trees, unicyclic, bicyclic, and tricyclic graphs in terms of co-independent liar’s domination number.



---

*Source: 5544559-2021-03-20.xml*