@article{4566,
  author = {Bing Gao},
  title = {Robustness of Pairwise Distances vs. Diameter in Graphs Under Edge Deletions},
  journal = {Digital Signal Processing and Artificial Intelligence for Automatic Learning},
  year = {2025},
  volume = {4},
  number = {3},
  doi = {https://doi.org/10.6025/dspaial/2025/4/3/95-112},
  url = {https://www.dline.info/dspai/fulltext/v4n3/dspaiv4n3_1.pdf},
  abstract = {This paper examines the robustness of distances and diameter in connected graphs under adversarial edge deletions that preserve connectivity. It introduces the concept of robustness: a distance or diameter is robust if it remains unchanged in all connected spanning subgraphs. The authors establish that testing whether the distance between two vertices is robust can be done in linear time, O(n + m), by showing it is equivalent to recognizing a new class of graphs two terminal series parallel graphs of fixed length. This characterization leverages a for bidden rooted minor (a diamond graph rooted at the two vertices) and adapts known recognition algorithms. In contrast, the problem of determining whether the diameter of a graph is robust is proven to be coNP complete via a reduction from the Hamiltonian Path problem. The paper highlights a striking complexity gap between pairwise distance robustness and diameter robustness, despite their apparent similarity. These results contribute to understanding the structural properties of graphs under dynamic or unreliable network conditions, with implications for resilient network design and distributed algorithms.},
}