Graphs which satisfy a Vizing-like bound for power domination of Cartesian products

Authors Sarah E. Anderson, Kirsti Kuenzel, Houston Schuerger

Publication date 8 September 2022

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 s u b s e t e q 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

,

g a m m a_{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 B o x 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}

,

g a m m a_{P} (T_{1}) g a m m a_{P} (T_{2}) l e q g a m m a_{P} (T_{1} B o x T_{2})

.

This page was built for publication: Graphs which satisfy a Vizing-like bound for power domination of Cartesian products

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