dc.creator | Moreno Casablanca, Rocío | es |
dc.creator | Dankelmann, Peter | es |
dc.creator | Goddard, Wayne | es |
dc.creator | Mol, Lucas | es |
dc.creator | Oellermann, Ortrud R. | es |
dc.date.accessioned | 2021-09-13T11:12:18Z | |
dc.date.available | 2021-09-13T11:12:18Z | |
dc.date.issued | 2021 | |
dc.identifier.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 | |
dc.identifier.issn | 1382-6905 | es |
dc.identifier.uri | https://hdl.handle.net/11441/125645 | |
dc.description.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 κ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. | es |
dc.format | application/pdf | es |
dc.format.extent | 28 | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | Journal of Combinatorial Optimization, 2021 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Connectivity | es |
dc.subject | Average connectivity | es |
dc.subject | Orientations | es |
dc.subject | Cubic graphs | es |
dc.subject | Minimally 2-connected graphs | es |
dc.subject | Maximal outerplanar graphs | es |
dc.title | The maximum average connectivity among all orientations of a graph | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.relation.publisherversion | https://link.springer.com/article/10.1007/s10878-021-00789-z | es |
dc.identifier.doi | 10.1007/s10878-021-00789-z | es |
dc.journaltitle | Journal of Combinatorial Optimization | es |
dc.publication.volumen | 2021 | es |