×

Generalized power domination in regular graphs. (English) Zbl 1290.05117

Authors’ abstract: In this paper, we continue the study of power domination in graphs (see [T. W. Haynes et al., SIAM J. Discrete Math. 15, No. 4, 519–529 (2002; Zbl 1006.05043); P. Dorbec et al., ibid. 22, No. 2, 554–567 (2008; Zbl 1171.05037); A. Aazami and K. Stilp, ibid. 23, No. 3, 1382–1399 (2009; Zbl 1209.68628)]). Power domination in graphs was birthed from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set following a set of rules (according to Kirchhoff laws) for power system monitoring. The minimum cardinality of a power dominating set of a graph is its power domination number. We show that the power domination of a connected cubic graph on \(n\) vertices different from \(K_{3,3}\) is at most \(n/4\) and this bound is tight. More generally, we show that for \(k \geq 1\), the \(k\)-power domination number of a connected \((k+2)\)-regular graph on \(n\) vertices different from \(K_{k+2,k+2}\) is at most \(n/(k+3)\), where the 1-power domination number is the ordinary power domination number. We show that these bounds are tight.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)