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

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/117013

Title:	Dominating 2-broadcast in graphs: complexity, bounds and extremal graphs
Author:	Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas González, María Luz
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
Abstract:	Limited dominating broadcasts were proposed as a variant of dominating broadcasts, where the broadcast function is upper bounded. As a natural extension of domination, we consider dominating 2-broadcasts along with the associated parameter, the dominating 2-broadcast number. We prove that computing the dominating 2-broadcast number is a NP-complete problem, but can be achieved in linear time for trees. We also give an upper bound for this parameter, that is tight for graphs as large as desired.
Abstract:	Peer Reviewed
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística -Graph, theory -Broadcast -domination -NP-complete decision problem -Grafs, Teoria de -Classificació AMS::05 Combinatorics::05C Graph theory
Rights:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Submitted version Article
Share: