Article
On average connectivity of the strong product of graphs
Author/s | 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) |
Publication Date | 2013 |
Deposit Date | 2018-01-24 |
Published in |
|
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 ... 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. |
Funding agencies | Ministerio de Educación y Ciencia (MEC). España Generalitat de Catalunya |
Project ID. | MTM2011-28800-C02-02
1298 SGR2009 |
Citation | Abajo Casado, M.E., Moreno Casablanca, R., Diánez Martínez, A.R. y García Vázquez, P. (2013). On average connectivity of the strong product of graphs. Discrete Applied Mathematics, 161 (18), 2795-2801. |
Files | Size | Format | View | Description |
---|---|---|---|---|
On average connectivity.pdf | 510.3Kb | [PDF] | View/ | |