Artículo
On the connectivity and restricted edge-connectivity of 3-arc graphs
Autor/es | Balbuena, Camino
García Vázquez, Pedro Montejano Cantoral, Luis Pedro |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2014-01-10 |
Fecha de depósito | 2024-02-07 |
Publicado en |
|
Resumen | 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 two in G.
Let ←→G denote the symmetric digraph of a graph G. The 3-arc
graph X(G) of a given graph ... 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 two in G. Let ←→G denote the symmetric digraph of a graph G. The 3-arc graph X(G) of a given graph G is defined to have vertices the arcs of ←→G . Two vertices (ay), (bx) are adjacent in X(G) if and only if (y, a, b, x) is a 3-arc of G. The purpose of this work is to study the edge-connectivity and restricted edge-connectivity of 3-arc graphs. We prove that the 3-arc graph X(G) of every connected graph G of minimum degree δ(G) ≥ 3 has edgeconnectivity λ(X(G)) ≥ (δ(G) − 1)2; and restricted edge- connectivity λ(2)(X(G)) ≥ 2(δ(G) − 1)2 − 2 if κ(G) ≥ 2. We also provide examples showing that all these bounds are sharp. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España European Commission (EC). Fondo Europeo de Desarrollo Regional (FEDER) Generalitat de Catalunya |
Identificador del proyecto | MTM2008-06620-C03-02/MTM
2009 SGR 1298 |
Cita | Balbuena, C., García Vázquez, P. y Montejano Cantoral, L.P. (2014). On the connectivity and restricted edge-connectivity of 3-arc graphs. Discrete Applied Mathematics, 162, 90-99. https://doi.org/10.1016/j.dam.2013.08.010. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On the connectivity and restricted ... | 489.0Kb | [PDF] | Ver/ | Versión aceptada |