Repositorio de producción científica de la Universidad de Sevilla

The Menger number of the strong product of graphs


Advanced Search
Opened Access The Menger number of the strong product of graphs

Show item statistics
Export to
Author: Abajo Casado, María Encarnación
Moreno Casablanca, Rocío
Diánez Martínez, Ana Rosa
García Vázquez, Pedro
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2013
Published in: Discrete Mathematics, 313 (13), 1490-1495.
Document type: Article
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.
Cite: Abajo Casado, M.E., Moreno Casablanca, R., Diánez Martínez, A.R. y García Vázquez, P. (2013). The Menger number of the strong product of graphs. Discrete Mathematics, 313 (13), 1490-1495.
Size: 463.9Kb
Format: PDF


DOI: 10.1016/j.disc.2013.03.002

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)