Graph theoretic reliability analysis for the Boolean n cube networks

Two graph-theoretic results concerning Boolean n-cube network reliability are presented. First, a simple formula for the number of spanning trees of the Boolean n-cube network is derived. As a result, the reliability function for large failure rate can be readily computed. Second, the Boolean n-cube network is proved to have the super-line-connectivity property. Thus the number of line-disconnecting sets (a set of lines the removal of which results in a disconnected or trivial graph) or order λ for the Boolean n -cube network is equal to 2ⁿ