Characterizing optimal monitoring edge-geodetic sets for some structured graph classes

DOI10.1016/J.DAM.2026.03.048MaRDI QIDQ7262696zbMATH OpenFDO

Authors Florent Foucaud, Arti Pandey, Kaustav K. Paul

Publication date 12 June 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.03.048

zbMATH Keywords

bipartite permutation graphstrongly chordal graphdistance-hereditary graph\(P_4\)-sparse graphmonitoring edge-geodetic set

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites work

• A linear-time algorithm for semitotal domination in strongly chordal graphs
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Algorithmic graph theory and perfect graphs
• Bipartite permutation graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
• Broadcast domination and multipacking in strongly chordal graphs
• Completely separable graphs
• Computing the cutwidth of bipartite permutation graphs in linear time
• Cycle Extendability of Hamiltonian Strongly Chordal Graphs
• Distance-based covering problems for graphs of given cyclomatic number
• Distance-hereditary graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Exploring algorithmic solutions for the independent Roman domination problem in graphs
• Monitoring edge-geodetic sets in graphs
• Monitoring edge-geodetic sets in graphs
• Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity
• Monitoring edge-geodetic sets: hardness and graph products
• Monitoring the edges of a graph using distances
• The geodetic number of a graph
• Topics in algorithmic graph theory
• Vertex deletion into bipartite permutation graphs
• Vertex-edge domination in interval and bipartite permutation graphs

This page was built for publication: Characterizing optimal monitoring edge-geodetic sets for some structured graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7262696)