Article
The maximum average connectivity among all orientations of a graph
Author/s | Moreno Casablanca, Rocío
![]() ![]() ![]() ![]() ![]() ![]() ![]() Dankelmann, Peter Goddard, Wayne Mol, Lucas Oellermann, Ortrud R. |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2021 |
Deposit Date | 2021-09-13 |
Published in |
|
Abstract | For distinct vertices u and v in a graph G, the connectivity between u and v, denoted κG(u,v), is the maximum number of internally disjoint u–v paths in G. The average connectivity of G, denoted κ¯¯¯(G), is the average of ... For distinct vertices u and v in a graph G, the connectivity between u and v, denoted κG(u,v), is the maximum number of internally disjoint u–v paths in G. The average connectivity of G, denoted κ¯¯¯(G), is the average of κG(u,v) taken over all unordered pairs of distinct vertices u, v of G. Analogously, for a directed graph D, the connectivity from u to v, denoted κD(u,v), is the maximum number of internally disjoint directed u–v paths in D. The average connectivity of D, denoted κ¯¯¯(D), is the average of κD(u,v) taken over all ordered pairs of distinct vertices u, v of D. An orientation of a graph G is a directed graph obtained by assigning a direction to every edge of G. For a graph G, let κ¯¯¯max(G) denote the maximum average connectivity among all orientations of G. In this paper we obtain bounds for κ¯¯¯max(G) and for the ratio κ¯¯¯max(G)/κ¯¯¯(G) for all graphs G of a given order and in a given class of graphs. Whenever possible, we demonstrate sharpness of these bounds. This problem had previously been studied for trees. We focus on the classes of cubic 3-connected graphs, minimally 2-connected graphs, 2-trees, and maximal outerplanar graphs. |
Citation | Moreno Casablanca, R., Dankelmann, P., Goddard, W., Mol, L. y Oellermann, O.R. (2021). The maximum average connectivity among all orientations of a graph. Journal of Combinatorial Optimization, 2021 |
Files | Size | Format | View | Description |
---|---|---|---|---|
Casablanca2021_Article_TheMaxi ... | 659.7Kb | ![]() | View/ | |