2025/10/07 by Wayne Ge, Ge, Wayne
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2510.06392
openalex publication_date 2025/10/07 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
In this paper, we introduce super-minimally k-connected graphs, those k-connected graphs in which no proper subgraph is k-connected. For k greater than or equal to three, this class lies strictly between the classes of minimally k-connected graphs and uniformly k-connected graphs. In particular, we determine the minimum number of degree-3 vertices in a super-minimally 3-connected graph, thereby extending a result of Halin on minimally 3-connected graphs. In addition, we determine the maximum number of edges in a super-minimally 3-connected graph, extending Xu's result for uniformly 3-connected graphs, and providing an analogue of Halin's result for minimally 3-connected graphs.