On average connectivity of the strong product of graphs
Copyright policy )On average connectivity of the strong product of graphs
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.
Ministerio de Educación y Ciencia MTM2011-28800-C02-02
Generalitat de Cataluña 1298 SGR2009
- Universidad de Sevilla (US) Spain
- University of Seville Spain
- University of Seville Spain
Maximally connected graphs, Connectivity, Extremal problems in graph theory, Average connectivity, Graph operations (line graphs, products, etc.), strong product of graphs, Average degree, Strong Product Graphs, maximally connected graphs, average degree, average connectivity
Maximally connected graphs, Connectivity, Extremal problems in graph theory, Average connectivity, Graph operations (line graphs, products, etc.), strong product of graphs, Average degree, Strong Product Graphs, maximally connected graphs, average degree, average connectivity
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!