Connectivity of orientations of 3-edge-connected graphs

DOI10.1016/J.EJC.2020.103292MaRDI QIDQ2662789zbMATH OpenOpenAlexFDO

Authors Florian Hoersch, Zoltán Szigeti

Publication date 14 April 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

deletable arcFrank numberNash-Williams theorem

Mathematics Subject Classification ID

Connectivity (05C40)

Abstract: We attempt to generalize a theorem of Nash-Williams stating that a graph has a $k$-arc-connected orientation if and only if it is $2k$-edge-connected. In a strongly connected digraph we call an arc {it deletable} if its deletion leaves a strongly connected digraph. Given a $3$-edge-connected graph $G$, we define its Frank number $f(G)$ to be the minimum number $k$ such that there exist $k$ orientations of $G$ with the property that every edge becomes a deletable arc in at least one of these orientations. We are interested in finding a good upper bound for the Frank number. We prove that $f(G)leq7$ for every $3$-edge-connected graph. On the other hand, we show that a Frank number of $3$ is attained by the Petersen graph. Further, we prove better upper bounds for more restricted classes of graphs and establish a connection to the Berge-Fulkerson conjecture. We also show that deciding whether all edges of a given subset can become deletable in one orientation is NP-complete.

Recommendations

• On Frank's conjecture on \(k\)-connected orientations
• On orienting graphs for connectivity: Projective planes and Halin graphs
• Strongly 2-connected orientations of graphs
• scientific article; zbMATH DE number 1146228
• Eulerian orientations and vertex-connectivity

Cites work

• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Combinatorial optimization. Theory and algorithms.
• Connections in combinatorial optimization
• Edge-Disjoint Spanning Trees of Finite Graphs
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• Simultaneous well-balanced orientations of graphs
• The complexity of satisfiability problems

Cited in

(9)

• On orienting graphs for connectivity: Projective planes and Halin graphs
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• On Frank's conjecture on \(k\)-connected orientations
• scientific article; zbMATH DE number 1933263 (Why is no real title available?)
• Complexity of (arc)-connectivity problems involving arc-reversals or deorientations
• Quest for graphs of Frank number 3
• Improved upper bound on the Frank number of 3-edge-connected graphs
• Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
• The Frank number and nowhere-zero flows on graphs

This page was built for publication: Connectivity of orientations of 3-edge-connected graphs

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