2023/05/03 by Jan Goedgebeur, Goedgebeur, Jan, Edita Máčajová +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2305.02133
openalex publication_date 2023/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An edge e of a graph G is called deletable for some orientation o if the restriction of o to G-e is a strong orientation. Inspired by a problem of Frank, in 2021 Hörsch and Szigeti proposed a new parameter for 3-edge-connected graphs, called the Frank number, which refines k-edge-connectivity. The Frank number is defined as the minimum number of orientations of G for which every edge of G is deletable in at least one of them. They showed that every 3-edge-connected graph has Frank number at most 7 and that in case these graphs are also 3-edge-colourable the parameter is at most 3. Here we strengthen both results by showing that every 3-edge-connected graph has Frank number at most 4 and that every graph which is 3-edge-connected and 3-edge-colourable has Frank number 2. The latter also confirms a conjecture by Barát and Blázsik. Furthermore, we prove two sufficient conditions for cubic graphs to have Frank number 2 and use them in an algorithm to computationally show that the Petersen graph is the only cyclically 4-edge-connected cubic graph up to 36 vertices having Frank number greater than 2.