Chordal Bipartite Analogs of $2$-Trees and Isolated Failure Immune Networks

Abstract

2-trees are defined recursively, starting from a single edge, by repeatedly erecting new triangles onto existing edges. These have been widely studied in connection with chordal graphs, series-parallel graphs, and isolated failure immune (IFI) networks.

A similar family, based on recursively erecting new $K_{2,h}$ subgraphs onto existing edges, is shown to have analogous connections to chordal bipartite graphs, series-parallel graphs, and a notion motivated by IFI networks.