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

Terry A. McKee1
1Department of Mathematics & Statistics Wright State University, Dayton, Ohio 45435

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.

Keywords: 2-trees; Chordal graphs; Series-parallel graphs; Chordal bipartite graphs; Isolated failure immune networks; IFI networks.