Klaus Dohmen, Peter Tittmann
Published 2011-03-20Version 1
We propose a new network reliability measure for some particular kind of service networks, which we refer to as domination reliability. We relate this new reliability measure to the domination polynomial of a graph and the coverage probability of a hypergraph. We derive explicit and recursive formulae for domination reliability and its associated domination reliability polynomial, deduce an analogue of Whitney's broken circuit theorem, and prove that computing domination reliability is NP-hard.
An Abstraction of Whitney's Broken Circuit Theorem
Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
An Inductive Proof of Whitney's Broken Circuit Theorem
![QR code for arXiv:1103.3854 [math.CO]](http://oss.arxitics.com/images/favicon.svg)