Monitoring edge-geodetic sets in graphs Subhadeep R. DevSanjana DeyFlorent FoucaudKrishna Narayanan Lekshmi Ramasubramony Sulochana

2025-05-02 0 0 657.08KB 15 页 10玖币

侵权投诉

Monitoring edge-geodetic sets in graphs

Subhadeep R. Dev∗Sanjana Dey†Florent Foucaud‡§ Krishna Narayanan¶‖

Lekshmi Ramasubramony Sulochana ‖

October 31, 2023

Abstract

We introduce a new graph-theoretic concept in the area of network monitoring. In this area,

one wishes to monitor the vertices and/or the edges of a network (viewed as a graph) in order to

detect and prevent failures. Inspired by two notions studied in the literature (edge-geodetic sets and

distance-edge-monitoring sets), we deﬁne the notion of a monitoring edge-geodetic set (MEG-set for

short) of a graph Gas an edge-geodetic set SĎVpGqof G(that is, every edge of Glies on some

shortest path between two vertices of S) with the additional property that for every edge eof G, there

is a vertex pair x, y of Ssuch that elies on all shortest paths between xand y. The motivation is

that, if some edge eis removed from the network (for example if it ceases to function), the monitoring

probes xand ywill detect the failure since the distance between them will increase.

We explore the notion of MEG-sets by deriving the minimum size of a MEG-set for some basic

graph classes (trees, cycles, unicyclic graphs, complete graphs, grids, hypercubes, corona products...)

and we prove an upper bound using the feedback edge set of the graph.

We also show that determining the smallest size of an MEG-set of a graph is NP-hard, even for

graphs of maximum degree at most 9.

1 Introduction

We introduce a new graph-theoretic concept, that is motivated by the problem of network monitoring,

called monitoring edge-geodetic sets. In the area of network monitoring, one wishes to detect or repair

faults in a network; in many applications, the monitoring process involves distance probes [2, 3, 4, 10].

Our networks are modeled by ﬁnite, undirected simple connected graphs, whose vertices represent systems

and whose edges represent the connections between them. We wish to monitor a network such that when

a connection (an edge) fails, we can detect the said failure by means of certain probes. To do this, we

select a small subset of vertices (representing the probes) of the network such that all connections are

covered by the shortest paths between pairs of vertices in the network. Moreover, any two probes are able

to detect the current distance that separates them. The goal is that, when an edge of the network fails,

some pair of probes detects a change in their distance value, and therefore the failure can be detected.

Our inspiration comes from two areas: the concept of geodetic sets in graphs and its variants [12], and

the concept of distance edge-monitoring sets [9, 10].

We now proceed with some necessary deﬁnitions. A geodesic is a shortest path between two vertices

u, v of a graph G[20]. The length of a geodesic between two vertices u, v in Gis the distance dGpu, vq

∗Indian Statistical Institute, Kolkata, India

†National University of Singapore, Singapore

‡Universit´e Clermont Auvergne, CNRS, Clermont Auvergne INP, Mines Saint-Etienne, LIMOS, 63000 Clermont-Ferrand,

France.

§Research ﬁnanced by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and by the ANR

project GRALMECO (ANR-21-CE48-0004).

¶Department of Mathematics, Simon Fraser University, Burnaby, Canada

‖PSG College of Technology, Coimbatore, India

arXiv:2210.03774v2 [math.CO] 29 Oct 2023

between them. For an edge eof G, we denote by G´ethe graph obtained by deleting efrom G. An edge e

in a graph Gis a bridge if G´ehas more connected components than G. The open neighborhood of a vertex

vPVpGqis NGpvq“tuPV|uv PEpGqu and its closed neighborhood is the set NGrvs “ NGpvqYtvu.

Monitoring edge-geodetic sets. We now formally deﬁne our main concept.

Deﬁnition 1.1. Two vertices x, y monitor an edge ein graph Gif ebelongs to all shortest paths between

xand y. A set Sof vertices of Gis called a monitoring edge-geodetic set of G(MEG-set for short) if,

for every edge eof G, there is a pair x, y of vertices of Sthat monitors e.

We denote by megpGqthe size of a smallest MEG-set of G. We note that VpGqis always an MEG-set

of G, thus megpGqis always well-deﬁned.

Related notions. A set Sof vertices of a graph Gis a geodetic set if every vertex of Glies on some

shortest path between two vertices of S[12]. An edge-geodetic set of Gis a set SĎVpGqsuch that every

edge of Gis contained in a geodesic joining some pair of vertices in S[19]. A strong edge-geodetic set of

Gis a set Sof vertices of Gsuch that for each pair u, v of vertices of S, one can select a shortest u´v

path, in a way that the union of all these `|S|

2˘paths contains EpGq[16]. It follows from these deﬁnitions

that any strong edge-geodetic set is an edge-geodetic set, and any edge-geodetic set is a geodetic set (if

the graph has no isolated vertices). In fact, every MEG-set is a strong edge-geodetic set. Indeed, given

an MEG-set S, one can choose any shortest path between each pair of vertices of S, and the set of these

paths covers EpGq. Indeed, every edge of Gis contained in all shortest paths between some pair of S.

Hence, MEG-sets can be seen as an especially strong form of strong edge-geodetic sets.

A set Sof vertices of a graph Gis a distance-edge monitoring set if, for every edge e, there is a vertex

xof Sand a vertex yof Gsuch that elies on all shortest paths between xand y[9, 10]. Thus, it follows

immediately that any MEG-set of a graph Gis also a distance-edge monitoring set of G.

Our results. We start by presenting some basic lemmas about the concept of MEG-sets in Section 2,

that are helpful for understanding this concept. We then study in Section 3 the optimal value of megpGq

when Gis a tree, cycle, unicyclic graph, complete (multipartite) graph, hypercubes, grids and corona

products. In Section 4, we show that megpGqis bounded above by a linear function of the feedback edge

set number of G(the smallest number of edges of Gneeded to cover all cycles of G, also called cyclomatic

number ) and the number of leaves of G. This implies that megpGqis bounded above by a function of the

max leaf number of G(the maximum number of leaves in a spanning tree of G). These two parameters

are popular in structural graph theory and in the design of algorithms. We refer to Figure 1 for the

relations between parameter meg and other graph parameters. We show that determining megpGqis an

NP-complete problem, even in graphs of maximum degree at most 9, in Section 5. Finally, we conclude

in Section 6.

Further related work on MEG-sets. This paper is the full version of a paper presented at the

CALDAM 2023 conference [11], where the notion of MEG-sets was presented for the ﬁrst time. It

contains the full proofs of the results in the conference version (with a corrected version of Theorem 3.5),

as well as the new result on corona products, and the new NP-completeness proof. In the meantime,

Haslegrave [14] proved that the MEG-set problem is NP-complete on general graphs, and also studied

MEG-sets for other graph products.

2 Preliminary lemmas

We now give some useful lemmas about the basic properties of MEG-sets.

A vertex is simplicial if its neighborhood forms a clique.

Lemma 2.1. In a graph Gwith at least one edge, any simplicial vertex belongs to any edge-geodetic set

and thus, to any MEG-set of G.

Vertex Cover Number

Max Leaf Number

Feedback Edge Set

Number meg

Feedback Vertex Set

Number Distance Edge-Monitoring

Number Strong Edge-Geodetic

Set Number

Edge-Geodetic

Set Number

Geodetic Set

Number

Arboricity

Figure 1: Relations between the parameter meg and other structural parameters in graphs (with no

isolated vertices). For the relationships of distance edge-monitoring sets, see [9, 10]. Arcs between

parameters indicate that the value of the bottom parameter is upper-bounded by a function of the top

parameter.

Proof. Let us consider by contradiction an MEG-set of Gthat does not contain said simplicial vertex v.

Any shortest path passing through its neighbors will not pass through v, because all the neighbors are

adjacent, hence leaving the edges incident to vuncovered, a contradiction.

Two distinct vertices uand vof a graph G are open twins if Npuq “ Npvqand closed twins if

Nrus “ Nrvs. Further, uand vare twins in Gif they are open twins or closed twins in G.

Lemma 2.2. If two vertices are twins of degree at least 1 in a graph G, then they must belong to any

MEG-set of G.

Proof. For any pair u, v of open twins in G, for any shortest path passing through u, there is another

one passing through v. Thus, if u, v were not part of the MEG-set, then the edges incident to uand v

would remain unmonitored, a contradiction.

If u, v are closed twins, if some shortest path contains the edge uv, then it must be of length 1 and

consist of the edge uv itself (otherwise there would be a shortcut). Thus, to monitor uv, both u, v must

belong to any MEG-set.

The next two lemmas concern cut-vertices and subgraphs, and will be useful in some of our proofs.

Lemma 2.3. Let Gbe a graph with a cut-vertex vand C1, C2, . . . , Ckbe the kcomponents obtained

when removing vfrom G. If S1, S2, . . . , Skare MEG-sets of the induced subgraphs GrC1Y tvus, GrC2Y

tvus, . . . , GrCkY tvus, then S“ pS1YS2,...,YSkqztvuis an MEG-set of G.

Proof. Consider any edge eof G, say in C1. Then, there are two vertices x, y of S1such that ebelongs

to all shortest paths between xand yin G1“GrC1Y tvus. Assume ﬁrst that vR tx, yu. All shortest

paths between xand yin Galso exist in G1. Thus, eis monitored by tx, yu Ď Sin G. Assume next that

vP tx, yu: without loss of generality, v“x. At least one edge exists in GrC2Y tvus, which implies that

S2ztvuis nonempty, say, it contains z. Then, eis monitored by yand z, since zPS. Thus, Smonitors

all edges of G, as claimed.

Lemma 2.4. Let Gbe a graph and Han induced subgraph of Gsuch that for all vertex pairs tx, yuin

H, no shortest path between them uses edges in G´H. Then, for any set Sof vertices of Gcontaining

an MEG-set of H, the edges of Hare monitored by Sin G.

Proof. Let Sbe an MEG-set of Gcontaining an MEG-set S1of H. Let ebe an edge in Hthat lies on all

shortest paths between some pair tx, yuof vertices of S1. By our hypothesis, no shortest path between x

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

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

10 玖币 0人已下载

立即下载

摘要：

Monitoringedge-geodeticsetsingraphsSubhadeepR.Dev∗SanjanaDey†FlorentFoucaud‡§KrishnaNarayanan¶‖LekshmiRamasubramonySulochana‖October31,2023AbstractWeintroduceanewgraph-theoreticconceptintheareaofnetworkmonitoring.Inthisarea,onewishestomonitortheverticesand/ortheedgesofanetwork(viewedasagraph)inorder...

展开>> 收起<<

Monitoring edge-geodetic sets in graphs Subhadeep R. DevSanjana DeyFlorent FoucaudKrishna Narayanan Lekshmi Ramasubramony Sulochana.pdf

共15页,预览3页

还剩页未读，继续阅读

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

Monitoring edge-geodetic sets in graphs Subhadeep R. DevSanjana DeyFlorent FoucaudKrishna Narayanan Lekshmi Ramasubramony Sulochana

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: