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.
Paru en janvier 2017 , 18 pages
Ce cahier a été révisé en avril 2018