Counting Power Domination Sets in Complete m-ary Trees

DOI10.20429/TAG.2023.100104MaRDI QIDQ5869879zbMATH OpenOpenAlexFDO

Authors Hays Whitlatch, Katharine Shultis, Olivia Ramirez, Michele Ortiz, Sviatlana Kniahnitskaya

Publication date 12 January 2023

Published in Theory and Applications of Graphs (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

power domination

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Abstract: Motivated by the question of computing the probability of successful power domination by placing k monitors uniformly at random, in this paper we give a recursive formula to count the number of power domination sets of size k in a labeled complete m-ary tree. As a corollary we show that the desired probability can be computed in exponential with linear exponent time.

Recommendations

• On the number of dominating sets in some classes of trees
• Trees with extremal numbers of dominating sets
• Total and paired-domination numbers of a tree
• scientific article; zbMATH DE number 7742929
• A note on the p-domination number of trees
• Trees with extremal numbers of \(k\)-dominating sets
• Some bounds on the \(p\)-domination number in trees
• A note on the total domination number of a tree
• On domination and reinforcement numbers in trees
• On the number of minimum dominating sets in trees

This page was built for publication: Counting Power Domination Sets in Complete m-ary Trees

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