Back to Search
Start Over
Graphs which satisfy a Vizing-like bound for power domination of Cartesian products
- Publication Year :
- 2022
-
Abstract
- Power domination is a two-step observation process that is used to monitor power networks and can be viewed as a combination of domination and zero forcing. Given a graph $G$, a subset $S\subseteq V(G)$ that can observe all vertices of $G$ using this process is known as a power dominating set of $G$, and the power domination number of $G$, $\gamma_P(G)$, is the minimum number of vertices in a power dominating set. We introduce a new partition on the vertices of a graph to provide a lower bound for the power domination number. We also consider the power domination number of the Cartesian product of two graphs, $G \Box H$, and show certain graphs satisfy a Vizing-like bound with regards to the power domination number. In particular, we prove that for any two trees $T_1$ and $T_2$, $\gamma_P(T_1)\gamma_P(T_2) \leq \gamma_P(T_1 \Box T_2)$.
- Subjects :
- Mathematics - Combinatorics
05C69, 05C70
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2209.03930
- Document Type :
- Working Paper