Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInfectious power domination of hypergraphs
113
0
0.0
(
0
)
Authors
Beth Bjorkman
Ask ChatGPT about the research
No Arabic abstract
The power domination problem seeks to find the placement of the minimum number of sensors needed to monitor an electric power network. We generalize the power domination problem to hypergraphs using the infection rule from Bergen et al: given an initial set of observed vertices, $S_0$, a set $Asubseteq S_0$ may infect an edge $e$ if $Asubseteq e$ and for any unobserved vertex $v$, if $Acup {v}$ is contained in an edge, then $vin e$. We combine a domination step with this infection rule to create emph{infectious power domination}. We compare this new parameter to the previous generalization by Chang and Roussel. We provide general bounds and determine the impact of some hypergraph operations.
rate research
Read More
Let $mathcal{H}$ be a hypergraph on a finite set $V$. A {em cover} of $mathcal{H}$ is a set of vertices that meets all edges of $mathcal{H}$. If $W$ is not a cover of $mathcal{H}$, then $W$ is said to be a {em noncover} of $mathcal{H}$. The {em noncover complex} of $mathcal{H}$ is the abstract simplicial complex whose faces are the noncovers of $mathcal{H}$. In this paper, we study homological properties of noncover complexes of hypergraphs. In particular, we obtain an upper bound on their Leray numbers. The bound is in terms of hypergraph domination numbers. Also, our proof idea is applied to compute the homotopy type of the noncover complexes of certain uniform hypergraphs, called {em tight paths} and {em tight cycles}. This extends to hypergraphs known results on graphs.
Power domination in graphs arises from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A power dominating set of a graph is a set of vertices that observes every vertex in the graph, following a set of rules for power system monitoring. A practical problem of interest is to determine the minimum number of additional measurement devices needed to monitor a power network when the network is expanded and the existing devices remain in place. In this paper, we study the problem of finding the smallest power dominating set that contains a given set of vertices X. We also study the related problem of finding the smallest zero forcing set that contains a given set of vertices X. The sizes of such sets in a graph G are respectively called the restricted power domination number and restricted zero forcing number of G subject to X. We derive several tight bounds on the restricted power domination and zero forcing numbers of graphs, and relate them to other graph parameters. We also present exact and algorithmic results for computing the restricted power domination number, including integer programs for general graphs and a linear time algorithm for graphs with bounded treewidth. We also use restricted power domination to obtain a parallel algorithm for finding minimum power dominating sets in trees.
The $k$-power domination problem is a problem in graph theory, which has applications in many areas. However, it is hard to calculate the exact $k$-power domination number since determining k-power domination number of a generic graph is a NP-complete problem. We determine the exact $k$-power domination number in two graphs which have the same number of vertices and edges: pseudofractal scale-free web and Sierpinski gasket. The $k$-power domination number becomes 1 for $kge2$ in the Sierpinski gasket, while the $k$-power domination number increases at an exponential rate with regard to the number of vertices in the pseudofractal scale-free web. The scale-free property may account for the difference in the behavior of two graphs.
The well-known notion of domination in a graph abstracts the idea of protecting locations with guards. This paper introduces a new graph invariant, the autonomous domination number, which abstracts the idea of defending a collection of locations with autonomous agents following a simple protocol to coordinate their defense using only local information.
We introduce a new bivariate polynomial ${displaystyle J(G; x,y):=sumlimits_{W in V(G)} x^{|W|}y^{|N(W)|}}$ which contains the standard domination polynomial of the graph $G$ in two different ways. We build methods for efficient calculation of this polynomial and prove that there are still some families of graphs which have the same bivariate polynomial.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
