Note on power propagation time and lower bounds for the power domination number

被引：8
作者：
Ferrero, Daniela [1 ]
Hogben, Leslie [2 ,3 ]
Kenter, Franklin H. J. [4 ]
Young, Michael [2 ]
机构：
[1] Texas State Univ, Dept Math, San Marcos, TX USA
[2] Iowa State Univ, Dept Math, Ames, IA 50011 USA
[3] Amer Inst Math, 600 E Brokaw Rd, San Jose, CA 95112 USA
[4] Rice Univ, Dept Computat & Appl Math, Houston, TX 77005 USA
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2017年 / 34卷 / 03期
关键词：
Power domination; Power propagation time; Propagation time; Time constraint; GRAPHS; PLACEMENT;
D O I：
10.1007/s10878-016-0103-z
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We present a counterexample to a lower bound for the power domination number given in Liao (J Comb Optim 31:725-742, 2016). We also define the power propagation time, using the power domination propagation ideas in Liao and the (zero forcing) propagation time in Hogben et al. (Discrete Appl Math 160:1994-2005, 2012).
引用
收藏
页码：736 / 741
页数：6
相关论文
共 11 条
  • [1] Aazami A., 2008, Hardness Results and Approximation Algorithms for Some Problems on Graphs
  • [2] Domination in graphs with bounded propagation: algorithms, formulations and hardness results
    Aazami, Ashkan
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 19 (04) : 429 - 456
  • [3] POWER-SYSTEM OBSERVABILITY WITH MINIMAL PHASOR MEASUREMENT PLACEMENT
    BALDWIN, TL
    MILI, L
    BOISEN, MB
    ADAPA, R
    [J]. IEEE TRANSACTIONS ON POWER SYSTEMS, 1993, 8 (02) : 707 - 715
  • [4] Zero forcing sets and the minimum rank of graphs
    Barioli, Francesco
    Barrett, Wayne
    Butler, Steve
    Cioaba, Sebastian M.
    Cvetkovic, Dragos
    Fallat, Shaun M.
    Godsil, Chris
    Haemers, Willem
    Hogben, Leslie
    Mikkelson, Rana
    Narayan, Sivaram
    Pryporova, Olga
    Sciriha, Irene
    So, Wasin
    Stevanovic, Dragan
    van der Holst, Hein
    Vander Meulen, Kevin N.
    Wehe, Amy Wangsness
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) : 1628 - 1648
  • [5] Benson K.F., ARXIV151002421
  • [6] The PMU placement problem
    Brueni, DJ
    Heath, LS
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (03) : 744 - 761
  • [7] Full control by locally induced relaxation
    Burgarth, Daniel
    Giovannetti, Vittorio
    [J]. PHYSICAL REVIEW LETTERS, 2007, 99 (10)
  • [8] Improved algorithms and complexity results for power domination in graphs
    Guo, Jiong
    Niedermeier, Rolf
    Raible, Daniel
    [J]. ALGORITHMICA, 2008, 52 (02) : 177 - 202
  • [9] Domination in graphs applied to electric power networks
    Haynes, TW
    Hedetniemi, SM
    Hedetniemi, ST
    Henning, MA
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (04) : 519 - 529
  • [10] Propagation time for zero forcing on a graph
    Hogben, Leslie
    My Huynh
    Kingsley, Nicole
    Meyer, Sarah
    Walker, Shanise
    Young, Michael
    [J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (13-14) : 1994 - 2005
12