Properties of minimum Isolated Line Failure Immune graphs with Hamiltonian cycle

This paper presents properties of an ILFI graph with Hamiltonian cycle. A graph which is immune to isolated line failures is called an Isolated Lien Failure Immune (ILFI) graph. The numbers of vertices and edges of a graph are represented by n and m, respectively. For a given n, an ILFI graph with the minimum number of edges is referred to as a minimum ILFI graph. The main result of this paper is the following. The number of edges of minimum ILFI graphs (n≥4) with Hamiltonian cycle is given by m=⌈(3n-2)/2⌉, where ⌈x⌉ is the smallest integer more than or equal to x. The authors have also shown some properties of minimum ILFI graphs. The results will be applicable to the reliable sparse network design. [In Japanese.]