2020/03/03 by Heinrich, Irene, Heller, Till, Schmidt, Eva +1
#05C40 #05C45 #05C75 #05C85 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2003.01498
If a biconnected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every biconnected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a tree-structure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear-time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle packings.