Artículo
Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs
Autor/es | Moreno Casablanca, Rocío
![]() ![]() ![]() ![]() ![]() ![]() ![]() Mol, Lucas Oellermann, Ortrud R. |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2021 |
Fecha de depósito | 2021-09-13 |
Publicado en |
|
Resumen | Let G be a (multi)graph of order n and let u, v be vertices of G. The maximum number
of internally disjoint u–v paths in G is denoted by κG(u, v), and the maximum number
of edge-disjoint u–v paths in G is denoted by λG(u, ... Let G be a (multi)graph of order n and let u, v be vertices of G. The maximum number of internally disjoint u–v paths in G is denoted by κG(u, v), and the maximum number of edge-disjoint u–v paths in G is denoted by λG(u, v). The average connectivity of G is defined by κ(G) = Σ κG(u, v)/ (n2 ) , and the average edge-connectivity of G is defined by λ(G) = Σ λG(u, v)/ (n2 ) , where both sums run over all unordered pairs of vertices {u, v} ⊆ V(G). A graph G is called ideally connected if κG(u, v) = min{deg(u), deg(v)} for all unordered pairs of vertices {u, v} of G. We prove that every minimally 2-connected graph of order n with largest average connectivity is bipartite, with the set of vertices of degree 2 and the set of vertices of degree at least 3 being the partite sets. We use this structure to prove that κ(G) < 9 4 for any minimally 2-connected graph G. This bound is asymptotically tight, and we prove that every extremal graph of order n is obtained from some ideally connected nearly regular graph on roughly n/4 vertices and 3n/4 edges by subdividing every edge. We also prove that λ(G) < 9 4 for any minimally 2-edge-connected graph G, and provide a similar characterization of the extremal graphs. |
Agencias financiadoras | Natural Sciences and Engineering Research Council of Canada (NSERC) |
Identificador del proyecto | RGPIN-2016-05237
![]() |
Cita | Moreno Casablanca, R., Mol, L. y Oellermann, O.R. (2021). Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs. Discrete Applied Mathematics, 289 (January 2021), 233-247. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Average connectivity of minimally ... | 440.5Kb | ![]() | Ver/ | |
Este registro aparece en las siguientes colecciones
Excepto si se señala otra cosa, la licencia del ítem se describe como: Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Items relacionados
Enseñando items relacionados por título, autor, creador y materia.
-
Artículo
On the connectivity and restricted edge-connectivity of 3-arc graphs
Balbuena, Camino; García Vázquez, Pedro; Montejano Cantoral, Luis Pedro (Elsevier, 2014-01-10)A 3 − arc of a graph G is a 4-tuple (y, a, b, x) of vertices such that both (y, a, b) and (a, b, x) are paths of length ...
-
Artículo
External Connection Versus Internal Connection in Dental Implantology. A Mechanical In Vitro Study
Fernández Asián, Ignacio Rafael; Martínez-González, Álvaro-José; Torres-Lagares, Daniel; Serrera Figallo, María de los Ángeles; Gutiérrez Pérez, José Luis (MDPI, 2019-10-15)Background: In today’s dentistry, implantology has become a therapeutic resource of choice in certain clinical situations. ...
-
Artículo
A Research Roadmap: Connected Health as an Enabler of Cancer Patient Support
Ruiz Signorelli, Gabriel; Lehocki, Fedor; Mora Fernández, Matilde; O'Neill, Gillian; O'Connor, Dominic; Brennan, Louise; Monteiro Guerra, Francisco; Rivero Rodríguez, Alejandro; Hors Fraile, Santiago; Muñoz Penas, Juan; Bonjorn Dalmau, Mercé; Mota, Jorge; Oliveira, Ricardo B.; Mrinakova, Bela; Putekova, Silvia; Muro, Naiara; Zambrana, Francisco; García Gómez, Juan M. (JMIR Publications, 2019)The evidence that quality of life is a positive variable for the survival of cancer patients has prompted the interest of ...