2023/05/15 by Florian Hörsch, Hörsch, Florian
Computer Science · Materials Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Supramolecular Self-Assembly in Materials
paper · pdf · doi:10.48550/arxiv.2305.08688
openalex publication_date 2023/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a given digraph D and distinct u,v ∈ V(D), we denote by λD(u,v) the local arc-connectivity from u to v. Further, we define the total arc-connectivity tac(D) of D to be ∑_\u,v\⊆ V(D)λD(u,v)+λD(v,u). We show that, given a graph G and an integer k, it is NP-complete to decide whether G has an orientation G satisfying tac(G)≥ k. This answers a question of Pekec. On the positive side, we show that the corresponding maximization problem admits a (2)/(3)-approximation algorithm.