Counting Power Domination Sets in Complete m-ary Trees

DOI10.20429/TAG.2023.100104zbMATH Open1506.05103arXiv2201.09111OpenAlexW4313561868MaRDI QIDQ5869879FDOQ5869879

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)

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.

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

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

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)

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)