OPTIMAL LOCATING-PAIRED-DOMINATING SETS IN KING GRIDS YUXUAN YANG

2025-04-26 0 0 638.69KB 15 页 10玖币

侵权投诉

OPTIMAL LOCATING-PAIRED-DOMINATING SETS IN KING

GRIDS

YUXUAN YANG

Abstract. In this paper, we continue the study of locating-paired-dominating

set, abbreviated LPDS, in graphs introduced by McCoy and Henning. Given

a ﬁnite or inﬁnite graph G= (V, E), a set S⊂Vis paired-dominating if

the induced subgraph G[S] has a perfect matching and every vertex in Vis

adjacent to a vertex in S. The other condition for LPDS requires that for any

distinct vertices u, v ∈V\S, we have N(u)∩S6=N(v)∩S. Motivated by

the conjecture of Kinawi, Hussain and Niepel, we prove the minimal density

of LPDS in the king grid is between 8/37 and 2/9, and we ﬁnd uncountable

many diﬀerent LPDS with density 2/9 in the king grid. These results partially

solve their conjecture.

1. Introduction

The concept of locating-paired-dominating sets was introduced by McCoy and

Henning [8] as an extension of paired-dominating sets [3, 4]. The problem of locating

monitoring devices in a system when every monitor is paired with a backup monitor

serves as the motivation for this concept.

Here are some basic deﬁnitions and notations. Let G= (V, E) be an undirected

graph. For a subset S⊂V,G[S] is a subgraph of Ginduced by S. For a vertex

vin G, the set NG(v) = {u∈V|uv ∈E}is called the open neighborhood of vand

NG[v] = NG(v)∪ {v}is the closed neighborhood of v. We may use N(v) and N[v]

for short if there is no ambiguity of the base graph G. And a set Sof vertices

is called dominating set of Gif for any v∈V,N[v]∩S6=∅. A dominating set

is called locating-dominating set if for any pair of distinct vertices v, u ∈V\S,

N[u]∩S6=N[v]∩S. A set Mof edges is called matching if they do not share

vertices for each two. A matching Mis a perfect matching if every vertex is incident

to an edge of M. A paired-dominating set of Gis a dominating set Swhose induced

subgraph G[S] contains a perfect matching (not necessarily induced). The set S

is said to be a locating-paired-dominating set, abbreviated LPDS, if Sis both a

paired-dominating set and a locating-dominating set.

It is optimal to make the size of the dominating set as small as possible. The

problem of ﬁnding an optimal locating-dominating set in an arbitrary graph is

known to be NP-complete [1]. Particular interest was dedicated to inﬁnite grids

as many processor networks have a grid topology [2] [5] [6] [10]. There was also

the corresponding study for LPDS. For instance, LPDS in inﬁnite square grids was

discussed in [9], and LPDS in inﬁnite triangular and king grids was discussed in [7].

Especially, Hussain, Niepel, and Kinawi guessed the density of an optimal LPDS

in the king grid is equal to 2/9 in [7], and they proved this number is between

3/14 and 2/9. Our results partially solve this conjecture. For example, we use the

Discharge Method to improve the lower bound to 8/37. See Section 3 for other

main results.

2010 Mathematics Subject Classiﬁcation. 05C69.

Key words and phrases. locating-paired-dominating sets, king grids, domination, discharge

method.

arXiv:2210.11838v1 [math.CO] 21 Oct 2022

2 YUXUAN YANG

2. preliminaries

In this section, we list several notations and backgrounds for this paper. Some

of them come from [7].

Deﬁnition (king grid).An inﬁnite graph G= (V, E)is called king grid, where

V=Z×Z. Two vertices are adjacent if and only if their Euclidean distance is less

or equal to √2.

Each vertex vin the king grid has 8 neighbors, and four of its neighbors are

with Euclidean distance √2 from v. We call them √2-neighbors of v. If two √2-

neighbors of vhave distance 2√2, we call them in the opposite position of each

other. The distance of two vertices u, v of a graph is the number of the edges in

the shortest path connecting uand v, which is denoted by d(u, v).

Deﬁnition (k-neighborhood).The k-neighborhood of vertex uin graph Gis deﬁned

as Nk

G[u] = {x∈V(G)|d(u, x)≤k}.

To avoid unnecessary complexity, in this paper when we consider inﬁnite graphs,

we always assume there is a universal upper bound M∈Z+of the degree, which

means for all v∈V,|NG(v)|6M. The king grid satisﬁes this condition for sure.

Deﬁnition (density).Given a graph G= (V, E), which can be ﬁnite or inﬁnite,

and a set S⊂V, the density of Sin Gis deﬁned as

D(S) = lim sup

k→∞

|S∩Nk

G[u]|

|Nk

G[u]|,(2.1)

where uis a vertex of G.

Note that the density D(S) is independent of the choice of the vertex u.

Hussain, Niepel, and Kinawi have proved the following result for the density of

an optimal LPDS in the king grid [7]. Here, the term “optimal” means the LPDS

has minimal density.

Theorem A. If Sis an optimal LPDS in the king grid and D(S)is the density of

S, then we have 3/14 6D(S)62/9.

Also, they gave a conjecture for this density [7].

Conjecture A. If Sis an optimal LPDS in the king grid and D(S)is the density

of S, then we have D(S)=2/9.

In this paper, we always assume G= (V, E) is the king grid and Sis a LPDS

of G. For convenience, we use the following notations. Fix an arbitrary perfect

matching Mon the induced subgraph G[S]. Denote

m:S→S(2.2)

to be a map that sends each vertex to its partner in M. In other words, we have

NM(v) = {m(v)}. Because of the lack of edge-transitivity in the king grids, we

have two diﬀerent types of pairs in M. We deﬁne

S1:= {v∈S||N(v)∩N(m(v))|= 2},

S2:= {v∈S||N(v)∩N(m(v))|= 4}.(2.3)

Remark that each pair in S1has Euclidean distance √2 and each pair in S2has

Euclidean distance 1, so we call them far pairs and close pairs, respectively. It’s

trivial to ﬁnd S=S1∪S2and S1∩S2=∅.

OPTIMAL LOCATING-PAIRED-DOMINATING SETS IN KING GRIDS 3

3. main results

Suppose Sis a LPDS of the king grid G, under the notation (2.3) in the last

section we have the following observation for the density of S1and S2.

Theorem 1. Suppose S1and S2have density D(S1)and D(S2)in G, then

3D(S1) + 9

2D(S2)>1.(3.1)

Theorem 2. Suppose S1and S2have density D(S1)and D(S2)in G, then

2D(S1)+5D(S2)>1.(3.2)

Remark that Theorem 1 has almost been indicated in [7], in which the idea called

“share” was used. We prove both Theorem 1 and Theorem 2 by using Discharge

Method. The latter one is the main work of this paper.

From these two theorems, we can easily improve the lower bound in Theorem A.

Corollary 1. The density of an optimal LPDS in the king grid is at least 8/37.

Proof. Suppose Sis a LPDS in G, then we have

D(S) = D(S1) + D(S2)

=3[14

3D(S1) + 9

2D(S2)] + [9

2D(S1)+5D(S2)]

37/2

>3+1

37/2

37.



Moreover, if we have a counterexample for Conjecture A, the fair pairs and close

pairs must both have positive density.

Corollary 2. Suppose Sis a LPDS in Gand D(S)<2/9, then D(S1)>0and

D(S2)>0.

Proof.

1614

3D(S1) + 9

2D(S2)

=14

3D(S1) + 9

2(D(S)−D(S1))

2D(S) + 1

6D(S1)

2·2

9+1

6D(S1).

169

2D(S1)+5D(S2)

2(D(S)−D(S2)) + 5D(S2)

2D(S) + 1

2D(S2)

2·2

9+1

2D(S2).



文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OPTIMALLOCATING-PAIRED-DOMINATINGSETSINKINGGRIDSYUXUANYANGAbstract.Inthispaper,wecontinuethestudyoflocating-paired-dominatingset,abbreviatedLPDS,ingraphsintroducedbyMcCoyandHenning.GivenaniteorinnitegraphG=(V;E),asetSVispaired-dominatingiftheinducedsubgraphG[S]hasaperfectmatchingandeveryvertexinV...

展开>> 收起<<

OPTIMAL LOCATING-PAIRED-DOMINATING SETS IN KING GRIDS YUXUAN YANG.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

OPTIMAL LOCATING-PAIRED-DOMINATING SETS IN KING GRIDS YUXUAN YANG

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: