On Frank's conjecture on \(k\)-connected orientations

DOI10.1016/j.jctb.2019.07.001zbMath1430.05065arXiv1212.4086OpenAlexW2963555739WikidataQ127529827 ScholiaQ127529827MaRDI QIDQ2284738

Olivier Durand de Gevigney

Publication date: 15 January 2020

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessvertex-connectivitygraph orientation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (8)

The maximum average connectivity among all orientations of a graph ⋮ On orientations maximizing total arc-connectivity ⋮ Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams ⋮ Complexity of (arc)-connectivity problems involving arc-reversals or deorientations ⋮ The complexity of 2-vertex-connected orientation in mixed graphs ⋮ Enumerating \(k\)-arc-connected orientations ⋮ Eulerian orientations and vertex-connectivity ⋮ Lexicographic Orientation Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Packing of rigid spanning subgraphs and spanning trees
• Strongly 2-connected orientations of graphs
• On minimally \((n,\lambda)\)-connected graphs
• Simultaneous well-balanced orientations of graphs
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• The complexity of satisfiability problems
• Two‐connected orientations of Eulerian graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control

This page was built for publication: On Frank's conjecture on \(k\)-connected orientations