On average connectivity of the strong product of graphs

Abajo E. Casablanca, Rocío M. Dianez A. Garcia-Vazquez P.
Discrete Applied Mathematics
Doi 10.1016/j.dam.2013.06.005
Volumen 161 páginas 2795 - 2801
2013-12-01
Citas: 4
Abstract
The average connectivity ??(G) of a graph G is the average, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. The connectivity ?(G) can be seen as the minimum, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. The connectivity and the average connectivity are upper bounded by the minimum degree ?(G) and the average degree d?(G) of G, respectively. In this paper the average connectivity of the strong product G1âŠG2 of two connected graphs G1 and G2 is studied. A sharp lower bound for this parameter is obtained. As a consequence, we prove that ??( G1âŠG2)=d?(G1⊠G2) if ??(Gi)=d?(Gi), i=1,2. Also we deduce that ?(G1âŠG2)= ?(G1âŠG2) if ?( Gi)=?(Gi), i=1,2. © 2013 Elsevier B.V. All rights reserved.
Average connectivity, Average degree, Maximally connected graphs, Strong product of graphs
Datos de publicaciones obtenidos de Scopus