Broadcast domination and multipacking in strongly chordal graphs

DOI10.1016/J.DAM.2018.08.021MaRDI QIDQ2414458zbMATH OpenOpenAlexFDO

Authors Gary MacGillivray, Feiran Yang, Richard C. Brewster

Publication date 17 May 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.08.021

zbMATH Keywords

broadcast dominationmultipackingstrongly chordal graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Linear programming (90C05)

Recommendations

• Broadcast domination on block graphs in linear time
• A linear‐time algorithm for broadcast domination in a tree
• scientific article; zbMATH DE number 2170461
• On the multipacking number of grid graphs
• Broadcast domination and multipacking: bounds and the integrality gap

Cites work

• A linear‐time algorithm for broadcast domination in a tree
• Broadcast domination on block graphs in linear time
• Broadcasts in graphs
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Dominating sets for split and bipartite graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Doubly lexical ordering of dense 0--1 matrices
• Doubly Lexical Orderings of Matrices
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 6843211 (Why is no real title available?)
• scientific article; zbMATH DE number 2109329 (Why is no real title available?)
• New bounds for the broadcast domination number of a graph
• On the difference between broadcast and multipacking numbers of graphs
• Optimal broadcast domination in polynomial time
• Radial trees
• Relations between packing and covering numbers of a tree
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Totally-Balanced and Greedy Matrices

Cited in

(17)

• On the complexity of broadcast domination and multipacking in digraphs
• Broadcast domination in subcubic graphs
• Broadcasts on paths and cycles
• Broadcast domination on block graphs in linear time
• Broadcast domination in graphs
• On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
• Broadcast domination and multipacking: bounds and the integrality gap
• On the multipacking number of grid graphs
• 2-limited broadcast domination on grid graphs
• Relation between broadcast domination and multipacking numbers on chordal graphs
• Proving exact values for the \(2\)-limited broadcast domination number on grid graphs
• An improved upper bound for the domination number of a graph
• Multipacking in the Euclidean metric space
• On the broadcast independence number of locally uniform 2-lobsters
• Multipacking and broadcast domination on cactus graphs and its impact on hyperbolic graphs
• Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs
• Characterizing optimal monitoring edge-geodetic sets for some structured graph classes

This page was built for publication: Broadcast domination and multipacking in strongly chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414458)