Article
On the connectivity and restricted edge-connectivity of 3-arc graphs
Author/s | Balbuena, Camino
García Vázquez, Pedro ![]() ![]() ![]() ![]() ![]() ![]() Montejano Cantoral, Luis Pedro |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2014-01-10 |
Deposit Date | 2024-02-07 |
Published in |
|
Abstract | 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. |
Funding agencies | Ministerio de Educación y Ciencia (MEC). España European Commission (EC). Fondo Europeo de Desarrollo Regional (FEDER) Generalitat de Catalunya |
Project ID. | MTM2008-06620-C03-02/MTM
![]() 2009 SGR 1298 ![]() |
Citation | 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
On the connectivity and restricted ... | 489.0Kb | ![]() | View/ | Versión aceptada |