Dominating 2-broadcast in graphs: complexity, bounds and extremal graphs

Applicable Analysis and Discrete Mathematics

article

J. Caceres¹  C. Hernando²  M. Mora²  I. M. Pelayo²  M. L. Puertas¹ 

[1] Department of Mathematics Universidad de Almer´ıa Almer´ıa;Department of Mathematics Universitat Polit`ecnica de Catalunya Barcelona

关键词: Broadcast;    Domination;    NP-complete decision problem;   

DOI  :  10.2298/AADM1801205C

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

Limited dominating broadcasts were proposed as a variant of dominatingbroadcasts, where the broadcast function is upper bounded. As a naturalextension of domination, we consider dominating 2-broadcasts along with theassociated parameter, the dominating 2-broadcast number. We prove thatcomputing the dominating 2-broadcast number is a NP-complete problem,but can be achieved in linear time for trees. We also give an upper boundfor this parameter, that is tight for graphs as large as desired.

【 授权许可】

Unknown