Characterizing the forbidden pairs for graphs to be super-edge-connected

Abstract

Let [Formula: see text] be a set of given connected graphs. A graph G is said to be [Formula: see text]-free if G contains no H as an induced subgraph for any [Formula: see text]. The graph G is super-edge-connected if each minimum edge-cut isolates a vertex in G. In this paper, except for some special graphs, we characterize all forbidden subgraph sets [Formula: see text] such that every [Formula: see text]-free graph is super-edge-connected for [Formula: see text] and 2.

Keywords

• Forbidden subgraphs
• super-edge-connectedness
• edge-connectivity