Groupe d’études et de recherche en analyse des décisions

G-2017-07

On the impact of one vertex or edge removal on distance-based invariants for Cartesian product graphs

, , , et

In this paper, we summarize some properties of the Cartesian product graphs related to degree and distance-based invariants. Then, we investigate how much a single edge or vertex removal in the Cartesian product of two connected graphs impacts: the distance between any pair of nodes, the average distance, the diameter and the maximum number of (simple, vertex-disjoint or edge-disjoint) shortest paths in the remaining graph.

, 18 pages