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.
Published January 2017 , 18 pages
This cahier was revised in April 2018
G1707R.pdf (300 KB)