Two-Terminal Reliability of the K4-Ladder—Revisited

The exact calculation of network reliability has been a practical, but difficult problem, solved for some periodic graphs—including ladders—using recursion and transfer matrices. We revisit the results for non-oriented K4-ladders of arbitrary length, using Markov chains (transition matrices) instead of recursion. We consider three cases, where the edges and vertices of the ladder have independent reliabilities: (i) \(p\) and \(1\) respectively (3 × 3 transition matrix); (ii) \(p\) and \(\rho\) respectively (4 × 4 transition matrix); (iii) varying throughout the ladder (6 × 6 transition matrices, indexed). To use transition matrices seems rather new in the context of graph reliability. These matrices have a clearer interpretation than their analogs, the transfer matrices, obtained from recursion: their entries represent probabilities to transit from one state to another when eliminating a K4 block. As a consequence, secondary results may be derived more easily—by modifying the initial and targeted states, or by invoking classical results in Markov chain theory.