The Menger number of the strong product of graphs

Abajo E. Casablanca, Rocío M. Dianez A. Garcia-Vazquez P.
Discrete Mathematics
Doi 10.1016/j.disc.2013.03.002
Volumen 313 páginas 1490 - 1495
2013-07-06
Citas: 2
Abstract
The xy-Menger number with respect to a given integer ?, for every two vertices x, y in a connected graph G, denoted by ??(x, y), is the maximum number of internally disjoint xy-paths whose lengths are at most ? in G. The Menger number of G with respect to ? is defined as ??(G) = min{??(x, y): x, y ? V(G)}. In this paper we focus on the Menger number of the strong product G1 × G2 of two connected graphs G1 and G2 with at least three vertices. We show that ??(G1 × G2) ? ??(G1) ??(G2) and furthermore, that ? ?+2(G1 × G2) ? ??(G1)??(G2) + ??(G1) + ??(G2) if both G1 and G2 have girth at least 5. These bounds are best possible, and in particular, we prove that the last inequality is reached when G1 and G2 are maximally connected graphs. © 2013 Elsevier B.V. All rights reserved.
Bounded edge-connectivity, Edge-deletion problem, Edge-fault-tolerant diameter, Menger number
Datos de publicaciones obtenidos de Scopus