Dominating and irredundant broadcasts in graphs
From MaRDI portal
Publication:507582
DOI10.1016/J.DAM.2016.12.012zbMATH Open1355.05189arXiv1608.00052OpenAlexW2503340257MaRDI QIDQ507582FDOQ507582
Authors: Yong-Cai Geng, Sumit K. Garg 
Publication date: 6 February 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: A broadcast on a nontrivial connected graph G=(V,E) is a function f from V(G) to {0,1,...,diam(G)} such that f(v) does not exceed the eccentricity of v. The cost of f is the sum of the function values. A broadcast f is dominating if each vertex of G is at distance at most f(v) from a vertex v with positive f(v). We use properties of minimal dominating broadcasts to define the concept of an irredundant broadcast on G. We determine conditions under which an irredundant broadcast is maximal irredundant. Denoting the minimum costs of dominating and maximal irredundant broadcasts by gamma_{b}(G) and ir_{b}(G) respectively, the definitions imply that ir_{b}(G) is bounded above by gamma_{b}(G) for all graphs. We show that gamma_{b} in turn is bounded above by (5/4)ir_{b}(G) for all graphs G. We also briefly consider the upper broadcast number Gamma_{b}(G) and upper irredundant broadcast number IR_{b}(G), and illustrate that the ratio IR_{b} to Gamma_{b} is unbounded for general graphs.
Full work available at URL: https://arxiv.org/abs/1608.00052
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Graph-theoretic parameters concerning domination, independence, and irredundance
- Properties of Hereditary Hypergraphs and Middle Graphs
- Broadcasts in graphs
- Optimal broadcast domination in polynomial time
- Radial trees
- Contributions to the theory of domination, independence and irredundance in graphs
- New bounds for the broadcast domination number of a graph
- Broadcast irredundance in graphs
- Title not available (Why is that?)
- A linear‐time algorithm for broadcast domination in a tree
Cited In (13)
- Broadcast domination in tori
- New bounds for the broadcast domination number of a graph
- Global dominating broadcast in graphs
- Broadcast irredundance in graphs
- Broadcast domination in graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the broadcast independence number of circulant graphs
- Broadcasts and domination in trees
- Upper broadcast domination number of caterpillars with no trunks
- On the difference between broadcast and multipacking numbers of graphs
- A note on bounds for the broadcast domination number of graphs
- Broadcasts on paths and cycles
This page was built for publication: Dominating and irredundant broadcasts in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507582)
