Domination reliability

zbMATH Open1243.05183arXiv1103.3854MaRDI QIDQ426770FDOQ426770

Authors: Klaus Dohmen, Peter Tittmann 

Publication date: 12 June 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1103.3854

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A Survey of Network Reliability and Domination Theory
• Publication:5749141
• (K, j)-domination and (K, j)-reliability
• Some Alternate Characterizations of Reliability Domination
• Network reliability

zbMATH Keywords

decompositionreliabilitydominationhypergraphNP-hardinclusion-exclusioncographbroken circuit

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65) Reliability, testing and fault tolerance of networks and computer systems (68M15) Stochastic network models in operations research (90B15)

Cited In (15)

• On the roots of domination polynomial of graphs
• The average domination polynomial of graphs is unimodal
• More on the unimodality of domination polynomial of a graph
• Optimal domination polynomials
• Neighborhood and domination polynomials of graphs
• Inclusion-exclusion by ordering-free cancellation
• Construction of dominating sets of certain graphs
• Subset-sum representations of domination polynomials
• Graph operations and neighborhood polynomials
• An abstraction of Whitney's broken circuit theorem
• Some Alternate Characterizations of Reliability Domination
• Title not available (Why is that?)
• On the domination polynomial of some graph operations
• Bipartition polynomials, the Ising model, and domination in graphs
• Directed network reliability: Domination and computing coefficients of the success‐marginal expansion

This page was built for publication: Domination reliability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426770)