Home > Research > Publications & Outputs > Monitoring edge-geodetic sets

Research

Associated organisational unit

Links

Text available via DOI:

Keywords

View graph of relations

Monitoring edge-geodetic sets: Hardness and graph products

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Monitoring edge-geodetic sets: Hardness and graph products. / Haslegrave, John.
In: Discrete Applied Mathematics, Vol. 340, 15.12.2023, p. 79-84.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Haslegrave, J 2023, 'Monitoring edge-geodetic sets: Hardness and graph products', Discrete Applied Mathematics, vol. 340, pp. 79-84. https://doi.org/10.1016/j.dam.2023.06.033

APA

Haslegrave, J. (2023). Monitoring edge-geodetic sets: Hardness and graph products. Discrete Applied Mathematics, 340, 79-84. https://doi.org/10.1016/j.dam.2023.06.033

Vancouver

Haslegrave J. Monitoring edge-geodetic sets: Hardness and graph products. Discrete Applied Mathematics. 2023 Dec 15;340:79-84. Epub 2023 Jul 18. doi: 10.1016/j.dam.2023.06.033

Author

Haslegrave, John. / Monitoring edge-geodetic sets : Hardness and graph products. In: Discrete Applied Mathematics. 2023 ; Vol. 340. pp. 79-84.

Bibtex

@article{232d53cc4db24beaad7fb7f51600c301,
title = "Monitoring edge-geodetic sets: Hardness and graph products",
abstract = "Foucaud, Krishna and Ramasubramony Sulochana recently introduced the concept of monitoring edge-geodetic sets in graphs, and a related graph invariant. These are sets of vertices such that the removal of any edge changes the distance between some pair of vertices in the set. They studied the minimum possible size of such a set in a given graph, which we call the monitoring edge-geodetic number.We show that the decision problem for the monitoring edge-geodetic number is NP-complete. We also give best-possible upper and lower bounds for the Cartesian and strong products of two graphs. These bounds establish the exact value in many cases, including many new examples of graphs whose only monitoring edge-geodetic set is the whole vertex set.",
keywords = "Edge monitoring, Geodetic problem, Shortest path, Cartesian product, Strong product, Computational complexity",
author = "John Haslegrave",
year = "2023",
month = dec,
day = "15",
doi = "10.1016/j.dam.2023.06.033",
language = "English",
volume = "340",
pages = "79--84",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Monitoring edge-geodetic sets

T2 - Hardness and graph products

AU - Haslegrave, John

PY - 2023/12/15

Y1 - 2023/12/15

N2 - Foucaud, Krishna and Ramasubramony Sulochana recently introduced the concept of monitoring edge-geodetic sets in graphs, and a related graph invariant. These are sets of vertices such that the removal of any edge changes the distance between some pair of vertices in the set. They studied the minimum possible size of such a set in a given graph, which we call the monitoring edge-geodetic number.We show that the decision problem for the monitoring edge-geodetic number is NP-complete. We also give best-possible upper and lower bounds for the Cartesian and strong products of two graphs. These bounds establish the exact value in many cases, including many new examples of graphs whose only monitoring edge-geodetic set is the whole vertex set.

AB - Foucaud, Krishna and Ramasubramony Sulochana recently introduced the concept of monitoring edge-geodetic sets in graphs, and a related graph invariant. These are sets of vertices such that the removal of any edge changes the distance between some pair of vertices in the set. They studied the minimum possible size of such a set in a given graph, which we call the monitoring edge-geodetic number.We show that the decision problem for the monitoring edge-geodetic number is NP-complete. We also give best-possible upper and lower bounds for the Cartesian and strong products of two graphs. These bounds establish the exact value in many cases, including many new examples of graphs whose only monitoring edge-geodetic set is the whole vertex set.

KW - Edge monitoring

KW - Geodetic problem

KW - Shortest path

KW - Cartesian product

KW - Strong product

KW - Computational complexity

U2 - 10.1016/j.dam.2023.06.033

DO - 10.1016/j.dam.2023.06.033

M3 - Journal article

VL - 340

SP - 79

EP - 84

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -