# On Locating-Dominating Set of Regular Graphs

Authors: Anuwar Kadir Abdul Gafur; Suhadi Wido Saputro
Journal: Journal of Mathematics
 (2021)

---

## Abstract

LetG be a simple, connected, and finite graph. For every vertex v∈VG, we denote by NGv the set of neighbours of v in G. The locating-dominating number of a graph G is defined as the minimum cardinality of W⊆VG such that every two distinct vertices u,v∈VG\W satisfies ∅≠NGu∩W≠NGv∩W≠∅. A graph G is called k-regular graph if every vertex of G is adjacent to k other vertices of G. In this paper, we determine the locating-dominating number of k-regular graph of order n, where k=n−2 or k=n−3.


---

## Body

## 1. Introduction

Given a simple, connected, and finite graphG. The neighbours of a vertex v of G are defined as the vertex set NGv=u∈VG|uv∈EG. A set of vertices W⊆VG is called a locating-dominating set of a graph G if every two distinct vertices u,v∈VG\W satisfies ∅≠NGu∩W≠NGv∩W≠∅. The minimum cardinality of locating-dominating sets of G is called the locating-dominating number of G, denoted by λG. This concept was introduced by Slater [1, 2].Let us model a building floor as a graph. Locating-dominating set can be used to determine an exact location of a fire alarm which sends a signal when detecting a fire in any of its adjacent vertices. The activated signals will univocally determine the place of the fire.Charon et al. [3] have proved that determining locating-dominating number of a graph is NP-complete problem which is reduced from 3-SAT. However, some results for certain classes of graphs have been obtained, such as paths [2], cycles [4], stars [5], complete graphs [6], bipartite graphs [7, 8], complete multipartite graphs [5], wheels [7], twin-free graphs [9, 10], and hypergraphs [11]. In [12], Balbuena et al. investigated a locating-dominating set of graphs with girth at least 5. In the other hand, Rajasekar and Nagarajan [13] studied the locating-dominating number of a graph containing a bridge.Furthermore, some authors have been characterized all graphs with a given locating-dominating number. Henning and Oellermann [6] have proved that for a connected graph G of order n≥2, λG=n−1 if and only if G is either complete graphs Kn or star graphs K1,n−1. They also characterized all graphs G of order n≥4 with locating-dominating number n−2. Meanwhile, Caceres et al. [7] have proved that there are 16 nonisomorphic graphs G satisfying λG=2.Some authors also have determined the locating-dominating number of graphs obtained from a product graphs. Canoy and Malacas [14] provided the lower and upper bounds for the locating-dominating number of corona product graphs. They also determined an exact value of the locating-dominating number of a composition of graphs between G and H where G is a connected totally point determining graph and H is a nontrivial connected graph. An exact value of the locating-dominating number of comb product of any two connected graphs of order at least two has been determined by Pribadi and Saputro [15]. Murtaza et al. [16] studied the locating-domination number of functigraphs of complete graphs. A study of a locating-dominating set of a graph by adding a universal vertex can be seen in [17].In this paper, we consider a regular graph. A graphG is called k-regular graph if every vertex in G is adjacent to k other vertices. Since every vertex of G is adjacent to the same number of vertices of G, every vertex of G has the same probability to distinguish some distinct vertices of G. Let G=V,E be a model of the multiprocessor system, such that VG is the set of processors and EG is the set of links between processors. Assume that at most one processor is malfunctioning and we want to test the system and find the faulty processor. Some processors can be chosen and assigned to check their neighbours. In case a selected processor detects a fault, it sends an alarm signal. Since we need an exact location of a faulty processor, we must choose some processors such that the chosen processors can uniquely tell the location of the malfunctioning processor. Then, a locating-dominating set of G can be used to choose those processors.Bertrand et al. [4] have initiated the study of the locating-dominating number on regular graph. They determined the locating-dominating number of 2-regular connected graphs (cycles). The locating-dominating number of n−1-regular graph of order n can be seen in [7]. In this paper, we determine the locating-dominating number of k-regular graph of order n where k=n−2 or k=n−3.The purpose of this paper is to further investigate the locating-dominating number of certain family of graphs, namely, to determine the locating-dominating number of certain regular graphs. We obtain two main results, one of them is the following result related with ann−2-regular graph.Theorem 1.
Forn≥4, let G be an n−2-regular graph. Then, λG=n/2.Our second result is related with ann−3-regular graph. In preparing the proof for the second result, we are able to obtain the intermediate result as follows.Theorem 2.
Form≥7, let H=Km\ECm. Then, λH=⌈2m−2/5⌉.Forn≥5, we consider certain cycles contained in a complete graph Kn. In this paper, we assume that a cycle contains at least three vertices. For r∈1,2,…,⌊n/3⌋, let R1,R2,…,Rr be r disjoint cycles contained in Kn such that VR1∪VR2∪⋯∪VRr=VKn. Note that an n−3-regular graph is isomorphic to KnER1∪ER2∪⋯∪ERr. In case r=1, the locating-dominating number of an n−3-regular graph of order at least 7 has been determined in Theorem 2. In Theorem 3, we provide the locating-dominating number of an n−3-regular graph of order n≥5 with 1≤r≤⌊n/3⌋.Theorem 3.
Forn≥5 and 1≤r≤⌊n/3⌋, let R1,R2,…,Rr be r disjoint cycles contained in Kn such that VR1∪VR2∪⋯∪VRr=VKn. For i∈1,2,…,r, let G=Kn\ER1∪ER2∪⋯∪ERr, mi=VRi, and Gi=Kmi\ERi. If k is the number of cycles Ri of order mi≥7 and mi≡1 or 3 (mod 5), then(1)λG=∑i=1rλGi,ifk≤1,k−1+∑i=1rλGi,ifk≥2.


## 2. (n−2)-Regular Graph and Proof of Theorem 1

Theorem1 is a direct consequence of Lemmas 1 and 2 in this section.In this section, we defineG as an n−2-regular graph of order n≥4. Note that if we count the sum of degree of all vertices, then every edge will be counted twice. Therefore, we have 2EG=nn−2. It implies that n must be even.Now, we can defineVG=xi,yi|1≤i≤n/2 and EG=uv|u,v∈VG\xiyi|1≤i≤n/2.Lemma 1.
LetW be a locating-dominating set of G. Then, for 1≤i≤n/2, xi∈W or yi∈W.Proof.
Suppose that there existsi∈1,2,…,n/2 such that xi,yi∉W. Note that every vertex in VGxi,yi is adjacent to both xi and yi. So, we will obtain that NGxi∩W=NGyi∩W, a contradiction.Lemma 2.
A vertex setxi|1≤i≤n/2 is a locating-dominating set of G.Proof.
LetS=xi|1≤i≤n/2. Then, VG\S=yi|1≤i≤n/2. Let us consider yi and yj for 1≤i<j≤n/2. Since xi∈NGyj but xi∉NGyi, we obtain ∅≠NGyi∩S≠NGyj∩S≠∅. Therefore, S is a locating-dominating set of G.


## 3. (n−3)-Regular Graph and Proof of Theorem 2

In this section, we defineG as an n−3-regular graph of order n≥5. Note that G contains a subgraph which is isomorphic to Km\ECm where m∈3,4,…,n. Let G′⊆G and G′=Km\ECm where m∈3,4,…,n. Then, every vertex in G′ is adjacent to all vertices of G\G′. In Lemma 3, we show that every subgraph is contributed to a locating-dominating set of G, which is a direct consequence of Observation 1 which has been proved by Henning and Oellermann [6].Observation 1 (see [6]).
LetW be a locating-dominating set of a connected graph G. If there exists two distinct vertices u,v∈VG such that dGu,z=dGv,z for all z∈VG\u,v, then u∈W or v∈W.Lemma 3.
Forn≥5, let G′⊆G and G′=Km\ECm where m∈3,4,…,n. If W is a locating-dominating set of G, then W∩VG′≠∅.
From Lemma3, we have Lemma 4.Lemma 4.
Forn≥5, let G′⊆G and G′=Km\ECm where m∈3,4,…,n. Let W be a locating-dominating set of G and W′=VG′∩W. Then, every two distinct vertices u,v∈VG′\W′ satisfies NG′u∩W′≠NG′v∩W′.Proof.
Suppose that there exists two distinct verticesu,v∈VG′\W′ such that NG′u∩W′=NG′v∩W′. Note that NG′u∩W′=NGu∩W′. Let G∗=G\G′ and W∗=W\W′. Since NGu∩VG∗=VG∗=NGv∩VG∗, we obtain NGu∩W=NGu∩W∗∪NGu∩W′=NGv∩W∗∪NGv∩W′=NGv∩W, a contradiction.By Lemma4, if W is a locating-dominating set of G, then we can say that VG′∩W is a locating-dominating set of a subgraph G′ of G. Note that, in this case, for u∈VG′, NG′u∩VG′∩W can be an empty set. In Lemma 5, we provide a locating-dominating set of a subgraph G′=Km\ECm of G where m∈3,4,5,6.Lemma 5.
Forn≥5, let G′⊆G and G′=Km\ECm where m∈3,4,5,6. Let W be a locating-dominating set of G. Then,(2)W∩VG′≥3,ifm=n=6,2,otherwise.
The lower bounds are sharp.Proof.
LetVG′=x1,x2,…,xm and ECm=x1x2,x2x3,…,xm−1xm,xmx1 where m∈3,4,5,6. We distinguish two cases.(1)
W∩VG′≥3 for m=n=6.In this case,G′=G. Suppose that W∩VG′≤2. Let W′ be a locating-dominating set of G′. Then, there exists u,v∈VG′\W′ such that either u≠v and NG′u∩W′=NG′v∩W′, or NG′u∩W′=∅, a contradiction.Now, we defineS=x1,x3,x5. Since NG′x2∩S=x5, NG′x4∩S=x1, and NG′x6∩S=x3, the vertex set S is a locating-dominating set of G′.(2)
W∩VG′≥2 for m≠6 or n≠6.Suppose thatW∩VG′≤1. If W∩VG′=0, then for two distinct vertices u,v∈VG′\W, NGu∩W=W=NGv∩W, a contradiction. So, we assume that W∩VG′=1. Let W∩VG′=xi with i∈1,2,…,m. Let xj and xk be two different vertices in G′ such that xjxi,xkxi∉EG′. So, NG′xj∩W=∅=NG′xk∩W. Since every vertex in G\G′ is adjacent to both xj and xk, we have NGxj∩W=W=NGxk∩W, a contradiction.For the sharpness, we define a vertex setSm as follows:(3)Sm=x1,x2,ifm∈3,4,5,x1,x3,ifm=6.
We will show thatSm is a locating-dominating set of a subgraph G′ of G. Let us consider vertices in VG′\Sm.(a)
m=3: we obtain that VG′\Sm=1. So, it is clear that Sm is a locating-dominating set of G′.(b)
m=4: we obtain that VG′\Sm=x3,x4. Note that NG′x3∩Sm=x1≠x2=NG′x4∩Sm. Therefore, Sm is a locating-dominating set of G′.(c)
m=5: we obtain that VG′\Sm=x3,x4,x5. It is easy to see that NG′x3∩Sm=x1, NG′x4∩Sm=x1,x2, and NG′x5∩Sm=x2. Therefore, it is clear that Sm is a locating-dominating set of G′.(d)
m=6: we obtain that VG′\Sm=x2,x4,x5,x6. It is easy to see that NG′x2∩Sm=∅, NG′x4∩Sm=x1, NG′x5∩Sm=x1,x3, and NG′x6∩Sm=x3. Therefore, it is clear that Sm is a locating-dominating set of G′.Remark 1.
We can say that the locating-dominating number ofG′ in Lemma 5 is given by(4)λG′=2,ifm∈3,4,5,6andn>m,3,ifn=m=6.
Now, let us considerG′⊆G and G′=Km\ECm for m≥7. Thus, the order of G must be n≥7. For n≥7, in order to determine a locating-dominating set of G′=Km\ECm for 7≤m≤n, we define some definitions. For u,v∈VG, let Pu,v be a shortest u,v-path in Cm. So, all edges in Pu,v are not element of EG′. Let W⊆VG′. For u,v∈W, let us consider the set of vertices of Pu,v\u,v. If all vertices of Pu,v\u,v are not in W, then the set of vertices in Pu,v\u,v is called a gap between u and v. Then, we called vertices u and v as the end points of gap. The two gaps are called neighbouring gaps if they have common end point. These definitions were firstly introduced by Buczkowski et al. [18]. They used this gap technique to determine the metric dimension of wheel graphs. In lemma 6, we provide the necessary and sufficient conditions for a locating-dominating set of G′ which is related to gap definition.Lemma 6.
Forn≥7, let G′=Km\ECm where m∈7,8,…,n. The vertex set W⊆VG′ is a locating-dominating set of G′ if and only if W satisfies all conditions as follows:(1)
Every gap with respect toW contains at most 3 vertices(2)
W contains at most one gap of 3 vertices(3)
IfA is a gap with respect to W, containing 2 or 3 vertices, then any neighbouring gaps of A have at most one vertexProof.
⇒ We will prove all three conditions by contradiction.(1)
Suppose that there exists a gap with respect toW containing at least 4 vertices.Leta1,a2,a3,a4∈VG′ where aiai+1∈ECm with 1≤i≤3 and all those vertices are not in W. Then, we have NG′a2∩W=W=NG′a3∩W, a contradiction.(2)
Suppose that there exists two gaps containing 3 vertices.Leta1,a2,a3 and b1,b2,b3 be two different gaps where aiai+1,bibi+1∈ECm with 1≤i≤2. Then, we have NG′a2∩W=W=NG′b2∩W, a contradiction.(3)
Suppose that there exists a neighbouring gap ofA containing at least 2 vertices.Leta1,a2,a3,a4,a5∈VG′ where aiai+1∈ECm with 1≤i≤4 and a3 is the only element of W among them. Then, we have NG′a2∩W=W\a3=NG′a4∩W, a contradiction.
⇐ Let S⊆VG′ satisfying all three conditions above. Since m≥7, we obtain S≥3. Now, we consider a vertex u∈VG′\S.(i)
u belongs to a gap containing one vertex.Leta and b be two end points of this gap. So, u is the only vertex which is not adjacent to a and b. Since S≥3 and for every vertex x∈VG′\S∪u, a∈NG′x or b∈NG′x, we obtain ∅≠NG′u∩S≠NG′x∩S≠∅.(ii)
u belongs to a gap containing two vertices.Leta and b be two end points of this gap. Without loss of generality, let au∈ECm. So, NG′u∩S=S\a. For x∈VG′\S∪u, if a∈NG′x, then ∅≠NG′u∩S≠NG′x∩S≠∅; otherwise, x belongs to a gap containing one vertex. From (i) above, we obtain that ∅≠NG′u∩S≠NG′x∩S≠∅.(iii)
u belongs to a gap containing three vertices.Letc1,c2,andc3 be a gap of three vertices where cici+1∈ECm with 1≤i≤2 and a and b be end points of this gap. Let ac1,bc3∈ECm. If u=c2, then NG′u∩S=S. Since u is the only vertex having this property, we obtain that for every vertex x∈VG′\S∪u and ∅≠NG′u∩S≠NG′x∩S≠∅. If u=c1, then NG′u∩S=S\a. For x∈VG′\S∪u, if a∈NG′x, then ∅≠NG′u∩S≠NG′x∩S≠∅; otherwise, x belongs to a gap containing one vertex. From (i) above, we obtain that ∅≠NG′u∩S≠NG′x∩S≠∅.Now, we are ready to prove Theorem2.Proof.
of Theorem2.
Form≥7, let H=Km\ECm where VH=x1,x2,…,xm and ECm=x1x2,x2x3,…,xm−1xm,xmx1. We distinguish two cases as follows:(1)
λH≤⌈2m−2/5⌉: we distinguish five cases of m as follows:(a)
m≡0mod5: let m=5k for an integer k≥2. Then, ⌈2m−2/5⌉=⌈10k−2/5⌉=2k. We define W=x2,x6∪x5i+3,x5i+6|1≤i≤k−2∪x5k−2,x5k. Since W=2k and satisfies all conditions in Lemma 6, then W is a locating-dominating set of H.(b)
m≡1mod5: let m=5k+1 for an integer k≥2. Then, ⌈2m−2/5⌉=⌈10k/5⌉=2k. We define W=x2,x6∪x5i+3,x5i+6|1≤i≤k−2∪x5k−2,x5k+1. Since W=2k and satisfies all conditions in Lemma 6, then W is a locating-dominating set of H.(c)
m≡2mod5: let m=5k+2 for an integer k≥1. Then, ⌈2m−2/5⌉=⌈10k+2/5⌉=2k+1. We define W=x2,x6∪x5i+3,x5i+6|1≤i≤k−1∪x5k+2. Since W=2k+1 and satisfies all conditions in Lemma 6, then W is a locating-dominating set of H.(d)
m≡3mod5: let m=5k+3 for an integer k≥1. Then, ⌈2m−2/5⌉=⌈10k+4/5⌉=2k+1. We define W=x2,x6∪x5i+3,x5i+6|1≤i≤k−1∪x5k+3. Since W=2k+1 and satisfies all conditions in Lemma 6, then W is a locating-dominating set of H.(e)
m≡4mod5: let m=5k+4 for an integer k≥1. Then, ⌈2m−2/5⌉=⌈10k+6/5⌉=2k+2. We define W=x2,x6∪x5i+3,x5i+6|1≤i≤k−1∪x5k+3,x5k+4. Since W=2k+2 and satisfies all conditions in Lemma 6, then W is a locating-dominating set of H.(2)
λH≥⌈2m−2/5⌉:  let S be a locating-dominating set of H with minimum cardinality. We consider two following cases:(a)
S is even.LetS=2k for a positive integer k. So, the number of gap of H with respect to S is 2k. Since S must be satisfy all conditions in Lemma 6, the number of gap containing at least 2 vertices is at most k. It follows that the number of vertex which is not in S is at most 3k+1. So, we obtain that k≥m−1/5. Therefore,(5)λH=S=2k≥2⋅m−15=2m−25.(b)
S is odd.LetS=2k+1 for a positive integer k. So, the number of gap of H with respect to S is 2k+1. Since S must be satisfy all conditions in Lemma 6, the number of gap containing at least 2 vertices is at most k. It follows that the number of vertex which is not in S is at most 3k+2. So, we obtain that k≥m−3/5. Therefore,(6)λH=S=2k+1≥2⋅m−35+1=2m−15≥2m−25.


## 4. (n−3)-Regular Graph and Proof of Theorem 3

Forn≥5, we consider certain cycles contained in a complete graph Kn. For 1≤r≤⌊n/3⌋, let R1,R2,…,Rr be r disjoint cycles contained in Kn such that VR1∪VR2∪⋯∪VRr=VKn. Note that an n−3-regular graph is isomorphic to Kn\ER1∪ER2∪⋯∪ERr. In case r=1, the locating-dominating number of an n−3-regular graph of order at least 7 has been determined in Theorem 2. Now, we will determine the locating-dominating number of an n−3-regular graph of order n≥5 with 1≤r≤⌊n/3⌋.LetG=Kn\ER1∪ER2∪⋯∪ERr and mi=VRi where 1≤i≤r. Let Gi be a subgraph of G where Gi=Kmi\ERi. Considering Lemma 4, a locating-dominating set of G consists of a locating-dominating set of Gi with 1≤i≤r. Therefore, we obtain that(7)λG≥λG1+λG2+⋯+λGr.Note that a locating-dominating ofG also must satisfy all three conditions in Lemma 6. Let W=∪i=1rWi where Wi is a locating-dominating set of Gi where Wi=λGi. If there exists distinct i,j∈1,2,…,r such that both locating-dominating sets Gi and Gj contain a gap of three vertices, then we must add at least one more vertex on W. So, we need to know the gap properties of a locating-dominating set of Gi.Lemma 7.
Forn≥5, let G be an n−3-regular graph. Let G′⊆G such that G′=Km\ECm with m∈3,4,…,n.(1)
Ifm=3, n>m=5, or m≡0,2,4mod5, then there exists a locating-dominating set of G′ where every gap contains at most two vertices.(2)
Ifm=n=5 or m≡1,3mod5 with m≠3, then a locating-dominating set of G′ has a gap containing three vertices.Proof.
First, letm=3, n>m=5, or m≡0,2,4mod5. Note that, in this case of m, we have G′⊂G. Let VG′=x1,x2,…,xm and ECm=x1x2,x2x3,…,xm−1xm,xmx1. We distinguish five cases as follows:(1)
m=3 or m=5: by Remark 1, λG′=2. We define W′=x1,x3.(2)
m=4: by Remark 1, λG′=2. We define W′=x1,x4.(3)
m≡0mod5: let m=5k for integer k≥2. By Theorem 2, λG′=2k. We define W′=x1,x4,x6,x9∪x5i+6,x5i+9|1≤i≤k−2.(4)
m≡2mod5:let m=5k+2 for integer k≥1. By Theorem 2, λG′=2k+1. We define W′=x1,x4,x6∪x5i+4,x5i+6|1≤i≤k−1.(5)
m≠4 and m≡4mod5: let m=5k+4 for integer k≥1. By Theorem 2, λG′=2k+2. We define W′=x1,x4,x6,x9∪x5i+6,x5i+9|1≤i≤k−1.
Note that every gap with respect toW′ above contains at most two vertices. Since W′ satisfies Lemma 6, then W′ is a locating-dominating set of G′.
Now, letm=n=5 or m≡1,3mod5 with m≠3. Suppose that every gap in G′ contains at most two vertices. We distinguish three cases as follows:(1)
m≡1mod5: let m=5k+1 for integer k≥1. By Theorem 2, λG′=2k. Let W be a locating-dominating set of G′ with 2k vertices. By Lemma 6, k gaps with respect to W, containing one vertex, and k other gaps with respect to W, containing two vertices. Thus, the total number of vertices of G′ which are not element of W is 3k. It follows that m=VG′\W+W=3k+2k=5k, a contradiction.(2)
m≠3 and m≡3mod5: let m=5k+3 for integer k≥1. By Theorem 2, λG′=2k+1. Let W be a locating-dominating set of G′ with 2k+1 vertices. By Lemma 6, k+1 gaps with respect to W, containing one vertex, and k other gaps with respect to W, containing two vertices. Thus, the total number of vertices of G′ which are not element of W is 3k+1. It follows that m=VG′\W+W=3k+1+2k=5k+1, a contradiction.(3)
m=n=5: thus, G=G′. Let VG′=x1,x2,…,x5 and EC5=x1x2,x2x3,…,x4x5,x5x1. By Remark 1, λG′=2. Since every gap in G′ contains at most two vertices, without loss of generality, let W be a locating-dominating set of G′ where W=x1,x3. Since NGx2=x4,x5, we obtain that NGx2∩W=∅, a contradiction.Now, we are ready to prove Theorem3.Proof.
of Theorem3.
The first case forλG is a direct consequence of Theorem 2, Lemmas 6 and 7, and Remark 1.For the last case, letHm1,Hm2,…,Hmk be disjoint k subgraphs of G such that Hmi=Kmi\ECmi where 1≤i≤k, mi≠3, and mi≡1 or 3mod5. Let Bi be a locating-dominating set of Hmi with λHmi vertices. By Lemma 7, Bi has a gap containing three vertices, say a1i,a2i,anda3i where ajiaj+1i∉EHmi with 1≤j≤2. We define Bi′=Bi∪a2i. It is easy to see that Bi′ is a locating-dominating set of Hmi which all the gaps contain at most two vertices. So, by using this property to subgraphs Hm1,Hm2,…,Hmk−1 of G, Theorem 2, Lemmas 6 and 7, and Remark 1, we prove the last case.



---

*Source: 8147514-2021-09-25.xml*