Characterizing Forbidden Pairs for the Edge-Connectivity of a Connected Graph to Be Its Minimum Degree

Abstract

Let H be a class of given graphs. A graph G is said to be H-free if G contains no induced copies of H for any H∈H. In this article, we characterize all connected subgraph pairs {R,S} guranteeing the edge-connectivity of a connected {R,S}-free graph to have the same minimum degree. Our result is a supplement of Wang et al. Furthermore, we obtain a relationship of forbidden sets when those general parameters have the recurrence relation.

Keywords

• forbidden subgraph
• edge-connectivity
• minimum degree
• parameter