On ‐connected graphs

DOI10.1002/JGT.22433zbMATH Open1417.05110arXiv1207.5357OpenAlexW2903198428MaRDI QIDQ5229537FDOQ5229537

Zoltán Szigeti, Olivier Durand de Gevigney

Publication date: 15 August 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: A graph G is called (2k, k)-connected if G is 2k-edge-connected and G-v is k-edge-connected for every vertex v. The study of (2k, k)-connected graphs is motivated by a conjecture of Frank which states that a graph has a 2-vertex-connected orientation if and only if it is (4, 2)-connected. In this paper, we provide a construction of the family of (2k, k)-connected graphs for k even which generalizes the construction given by Jord'an for k = 2. We also solve the corresponding connectivity augmentation problem: given a graph G and an integer k geq 2, what is the minimum number of edges to be added to make G (2k, k)-connected. Both these results are based on a new splitting-off theorem for (2k, k)-connected graphs.

Full work available at URL: https://arxiv.org/abs/1207.5357

zbMATH Keywords

connectivityorientationconnectivity augmentationsplitting-off

Mathematics Subject Classification ID

Connectivity (05C40)

Cited In (10)

• 2-connected and 2-edge-connected Steinhaus graphs
• The \((2, k)\)-connectivity augmentation problem: algorithmic aspects
• On \(k\)-critical \(2 k\)- connected graphs
• On perfectly two-edge connected graphs
• Note on the vertex 2–connectivity of a graph
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Globally Rigid Augmentation of Rigid Graphs
• On \(k\)-connected-homogeneous graphs
• Two paths joining given vertices in \(2k\)-edge-connected graphs
• On the Euler genus of a 2-connected graph

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On Graphs with Proper Connection Number 2 👍 👎
• On \(k\)-critical \(2 k\)- connected graphs 👍 👎
• On perfectly two-edge connected graphs 👍 👎
• On \(k\)-chromatically connected graphs 👍 👎
• On the structure of a \(k\)-connected graph 👍 👎
• On \(k\)-connected-homogeneous graphs 👍 👎
• On connected 2-\(K_n\)-residual graphs 👍 👎

This page was built for publication: On ‐connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229537)