The number of edges in critical strongly connected graphs

1999/11/16 by Ron Aharoni, Eli Berger, Aharoni, Ron +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis #math.CO

paper · pdf · doi:10.48550/arxiv.math/9911113

5 pages, no figures, given at the Eleventh Haifa Matrix Theory Conference 26.5.1999 Accepted at Discrete Math. v1 is the submitted version, v2 is the version after the referee's corrections. Note the main correction: the result for edge critical strongly connected graphs is already known

openalex publication_date 1999/11/16 · arxiv created 1999/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the maximal number of directed edges in a vertex-critical strongly connected simple digraph on n vertices is n(n-1)/2 - n +4.

Related

• On the maximum number of edges in k-critical graphs
• A lower bound on the number of edges in DP-critical graphs
• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• A lower bound on the number of edges in DP-critical graphs. II. Four colors
• Critical digraphs with few vertices