Group for Research in Decision Analysis

G-2017-07

On the number of shortest paths in Cartesian product graphs and its robustness

, , , , and

In this paper, we establish the maximum number of basic shortest paths in Cartesian product graphs and bounds on the maximum number of the vertex-disjoint shortest paths and on this of the edge-disjoint shortest paths. To the best of our knowledge, the class of Cartesian product graphs has been intensively studied according to various invariants, except the maximum number of (basic, vertex-disjoint or edge-disjoint) shortest paths, whereas the latter invariants were investigated for other graph classes. The main contribution of this paper is to fill this gap. Moreover, we investigate the impact of a vertex or an edge removal on the maximum number of basic shortest paths in Cartesian product graphs.

, 18 pages

This cahier was revised in April 2018