Component Order Edge Connectivity, Vertex Degrees, and Integer Partitions

Abstract

Given a finite, simple graph G, the k-component order connectivity (resp. edge connectivity) of G is the minimum number of vertices (resp. edges) whose removal results in a subgraph in which every component has an order of at most k − 1. In general, determining the k-component order edge connectivity of a graph is NP-hard. We identify conditions on the vertex degrees of G that can be used to imply a lower bound on the k-component order edge connectivity of G. We will discuss the process for generating such conditions for a lower bound of 1 or 2, and we explore how the complexity increases when the desired lower bound is 3 or more. In the process, we provide new proofs of related results concerning k component order connectivity, and we prove some relevant results about integer partitions.

Keywords

• component order connectivity
• component order edge connectivity
• degree sequence
• best monotone
• integer partition