The geodesic cover problem for butterfly networks Paul ManuelaSandi Klavˇ zarbcdR. Prabhae Andrew Arokiarajf

2025-05-06 0 0 1.63MB 18 页 10玖币

侵权投诉

The geodesic cover problem for butterﬂy networks

Paul ManuelaSandi Klavˇzarb,c,d R. Prabhae

Andrew Arokiarajf

aDepartment of Information Science, College of Computing Science and

Engineering, Kuwait University, Kuwait

pauldmanuel@gmail.com, p.manuel@ku.edu.kw

bFaculty of Mathematics and Physics, University of Ljubljana, Slovenia

sandi.klavzar@fmf.uni-lj.si

cFaculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

dInstitute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

eDepartment of Mathematics, Ethiraj College for Women, Chennai, Tamilnadu,

India

prabha75@gmail.com

fDepartment of Mathematics, School of Science and Humanities, Shiv Nadar

University Chennai, Kalavakkam, India

andrew23610032@snuchennai.edu.in

Abstract

A geodesic cover, also known as an isometric path cover, of a graph is a

set of geodesics which cover the vertex set of the graph. An edge geodesic

cover of a graph is a set of geodesics which cover the edge set of the graph.

The geodesic (edge) cover number of a graph is the cardinality of a minimum

(edge) geodesic cover. The (edge) geodesic cover problem of a graph is to

ﬁnd the (edge) geodesic cover number of the graph. Surprisingly, only partial

solutions for these problems are available for most situations. In this paper

we demonstrate that the geodesic cover number of the r-dimensional butterﬂy

is ⌈(2/3)2r⌉and that its edge geodesic cover number is 2r.

Keywords: isometric path; geodesic cover; edge geodesic cover; bipartite graph,

butterﬂy network

AMS Subj. Class. (2020): 05C12, 05C70

arXiv:2210.12675v2 [math.CO] 3 Dec 2024

1 Introduction

Let G= (V(G), E(G)) be a graph. The distance d(x, y) between vertices x, y ∈V(G)

is the length of a shortest x, y-path in G; any such path is called a geodesic. The

diameter diam(G) of Gis the maximum distance between any pair of vertices in G,

that is, diam(G) = maxu,v dG(u, v). A subgraph Hof Gis isometric if dG(x, y) =

dH(x, y) for all x, y ∈V(H).

Ageodesic cover of a graph Gis a set Sof geodesics such that each vertex of

Gbelongs to at least one geodesic of S. It is popularly known as isometric path

cover [4,5,8,9, 12]. The geodesic cover problem is one of the fundamental problems

in graph theory. The concept of geodesic cover is widely used in social networks,

computer networks, and ﬁxed interconnection networks [8]. Throughout this paper,

Z(G) denotes the set of all geodesics of Gand M(G) denotes the set of all maximal

(with respect to inclusion) geodesics of G.

Given Y⊆Z(G) and S⊆V(G), a geodesic cover of the triple (Y, S, G) is a set

of geodesics of Ythat cover S. Given Y⊆Z(G) and S⊆V(G), the geodesic cover

number of (Y, S, G), gcover(Y, S, G), is the minimum number of geodesics of Ythat

cover S. Note that there exist situations where gcover(Y, S, G) may not exist.

When Y⊆Z(G) and S=V, gcover(Y, V, G) is denoted by gcover(Y, G).

When Y=Z(G) and S⊆V, gcover(Z(G), S, G) is denoted by gcover(S, G).

When Y=Z(G) and S=V, gcover(Z(G), V, G) is denoted by gcover(G).

Given Y⊆Z(G) and S⊆V(G), the geodesic cover problem of (Y, S) is to ﬁnd

gcover(Y, S, G) of G. The geodesic cover problem of Gis to ﬁnd gcover(G) of G. An

edge geodesic cover of a graph is a set of geodesics which cover the edge set of the

graph. The edge geodesic cover number of a graph G, gcovere(G), is the cardinality

of a minimum edge geodesic cover. The edge geodesic cover problem of a graph Gis

to ﬁnd gcovere(G).

The geodesic cover problem is known to be NP-complete [2,14]. Apollonio et al.

[1] have studied induced path covering problems in grids. Fisher and Fitzpatrick [3]

have shown that the geodesic cover number of the (r×r)-dimensional grid is ⌈2r/3⌉.

The geodesic cover number of the (r×s)-dimensional grid is swhen r≥s(s−1),

cf. [9]. On the other hand, the complete solution of the geodesic cover problem

for the two-dimensional grid is still unknown, cf. [9]. There is no literature for the

geodesic cover problem on multi-dimensional grids.

The geodesic cover problems for cylinder and r-dimensional grids are discussed

in [9]. In particular, the isometric path cover number of the (r×r)-dimensional torus

is rwhen ris even, and is either ror r+ 1 when ris odd. In [11], the geodesic cover

problem was studied on block graphs, while in [12] it was investigated on complete

r-partite graphs and Cartesian products of two or three complete graphs.

Fitzpatrick et al. [4, 5] have shown that the geodesic cover number of the hyper-

cube Qris at least 2r/(r+ 1) and they have provided a partial solution when r+ 1

is a power of 2. The complete solution for the geodesic cover number of hypercubes

is also not yet known, cf. [4, 5, 8]. Manuel [9] has proved that the geodesic cover

number of the r-dimensional Benes network is 2r. In [8,9] the (edge) geodesic cover

problem of butterﬂy networks was stated as an open problem. In this paper we solve

these two problems.

2 Preliminaries

The results discussed in this section will be used as tools to prove the key results of

this paper.

Lemma 2.1. If Gis a connected graph, then the following hold.

(i) If S′⊆S′′ ⊆V(G)and Y⊆Z(G), then gcover(Y, S′′ , G)≥gcover(Y, S′, G).

(ii) If Y′⊆Y′′ ⊆Z(G)and S⊆V(G), then gcover(Y′′ , S, G)≤gcover(Y′, S, G).

(iii) gcover(G) = gcover(M(G), G).

Proof. Assertions (i) and (ii) are straightforward, hence we consider only (iii). Since

M(G)⊆Z(G), (ii) implies gcover(G) = gcover(Z(G), V, G)≤gcover(M(G), V, G) =

gcover(M(G), G). Since each geodesic is a subpath of some maximal geodesic, for

each geodesic cover Sof Z(G), there exists a geodesic cover S′of M(G) such that

|S|=|S′|. Therefore, gcover(Z(G), V, G)≥gcover(M(G), V, G) and consecutively

gcover(G) = gcover(Z(G), V, G)≥gcover(M(G), V, G) = gcover(M(G), G).

Proposition 2.2. If Kr,r,r≥2, is a complete bipartite graph, then gcover(Kr,r) =

⌈(2/3)r⌉.

Proof. Clearly, each maximal geodesic of Kr,r is a (diametral) path of length 2.

Therefore, gcover(Kr,r )≥ ⌈(2/3)r⌉. On the other hand, it is a simple exercise to

construct a geodesic cover of cardinality ⌈(2/3)r⌉.

Butterﬂy is considered as one of the best parallel architectures [6,7,15]. For r≥3,

the r-dimensional butterﬂy network BF (r) has vertices [j, s], where s∈ {0,1}rand

j∈ {0,1, . . . , r}. The vertices [j, s] and [j′, s′] are adjacent if j′=j+ 1, and either

s=s′or sand s′diﬀer precisely in the jth bit. BF (r) has (r+ 1)2rvertices and

r2r+1 edges. A vertex [j, s] is at level jand row s. There are two standard graphical

representations for BF(r), normal representation and diamond representation, see

Fig. 1.

Estimating the lower bound of gcover(BF(r)) in Section 3.1, we will use the dia-

mond representation of BF(r), while estimating the upper bound of gcover(BF(r))

in Section 3.2, the normal representation of BF(r) will be used.

Figure 1: (a) Normal representation of BF(3) (b) Diamond representation of BF(3).

Lemma 2.3. A geodesic of BF(r)contains at most two vertices of level 0and at

most two vertices of level r. Moreover, if a geodesic contains two vertices of level 0,

then they are the ends of the geodesic (and similarly for level r).

Proof. Let us assume that there exists a geodesic Pwhich contains more than two

vertices of level 0, say vi, vj, and vk. See Fig. 2(b). Then one of these three vertices

must be an internal vertex of P, say vj. The deletion of the vertices at level 0 from

BF(r) disconnects BF(r) into two vertex disjoint components G1and G2, where

both G1and G2are isomorphic to BF(r−1), cf. [7, 13, 16]. Since vjis an internal

vertex of Pand of degree 2, its neighbors vj−1and vj+1 also lie in P. Moreover,

one of the adjacent vertices vj−1,vj+1 lie in G1and the other lie in G2. Also, vi

has two adjacent vertices, say vi−1∈V(G1) and vi+1 ∈V(G2). Since G1and G2

are isomorphic, the vi−1, vj−1-geodesic and the vi+1, vj+1-geodesic are isomorphic,

which in turn implies that d(vi, vj−1) = d(vi, vj+1). This is not possible as Pis a

geodesic.

As the butterﬂy network is symmetrical with respect to level 0, it is symmetrical

with respect to level r, cf. [7,13,16]. Using the logic of the proof of Lemma 2.3, one

can prove the following.

Corollary 2.4. If both end vertices of a geodesic Pof BF(r)are either at level 0

or at level r, then Pis maximal.

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

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

10 玖币 0人已下载

立即下载

摘要：

ThegeodesiccoverproblemforbutterflynetworksPaulManuelaSandiKlavˇzarb,c,dR.PrabhaeAndrewArokiarajfaDepartmentofInformationScience,CollegeofComputingScienceandEngineering,KuwaitUniversity,Kuwaitpauldmanuel@gmail.com,p.manuel@ku.edu.kwbFacultyofMathematicsandPhysics,UniversityofLjubljana,Sloveniasandi....

展开>> 收起<<

The geodesic cover problem for butterfly networks Paul ManuelaSandi Klavˇ zarbcdR. Prabhae Andrew Arokiarajf.pdf

共18页,预览4页

还剩页未读，继续阅读

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

The geodesic cover problem for butterfly networks Paul ManuelaSandi Klavˇ zarbcdR. Prabhae Andrew Arokiarajf

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: