Dynamic approach to k-forcing

DOI10.20429/TAG.2015.020202MaRDI QIDQ5225512zbMATH OpenOpenAlexFDO

Authors Yair Caro, Ryan Pepper

Publication date 22 July 2019

Published in Theory and Applications of Graphs (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1405.7573

zbMATH Keywords

$k$-forcing numbergreedy algorithmzero forcing number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: The k-forcing number of a graph is a generalization of the zero forcing number. In this note, we give a greedy algorithm to approximate the k-forcing number of a graph. Using this dynamic approach, we give corollaries which improve upon two theorems from a recent paper of Amos, Caro, Davila and Pepper [2], while also answering an open problem posed by Meyer [9].

Recommendations

• On tight bounds for the \(k\)-forcing number of a graph
• Upper bounds on the \(k\)-forcing number of a graph
• Proof of a conjecture on the zero forcing number of a graph
• k-forcing number for Cartesian product of some graphs
• Extremal k-forcing sets in oriented graphs

Cited in

(30)

• On a conjecture of Gentner and Rautenbach
• On the total forcing number of a graph
• The zero forcing polynomial of a graph
• A computational study of \(f\)-reversible processes on graphs
• Bounds on the connected forcing number of a graph
• Total forcing versus total domination in cubic graphs
• Complexity and computation of connected zero forcing
• Zero forcing versus domination in cubic graphs
• On the zero forcing number and spectral radius of graphs
• Total forcing sets and zero forcing sets in trees
• From the editor-in-chief
• On the zero forcing number of a graph involving some classical parameters
• Zero forcing in claw-free cubic graphs
• Extremal k-forcing sets in oriented graphs
• Proof of a conjecture on the zero forcing number of a graph
• The Zero Forcing Number of Graphs
• The forcing number of graphs with given girth
• Upper bounds on the \(k\)-forcing number of a graph
• Zero forcing number of a graph in terms of the number of pendant vertices
• scientific article; zbMATH DE number 7528059 (Why is no real title available?)
• Immune sets in monotone infection rules. Characterization and complexity
• UPPER BOUNDS ON THE SEMITOTAL FORCING NUMBER OF GRAPHS
• On graphs maximizing the zero forcing number
• Bounding the total forcing number of graphs
• Bounds on zero forcing using (upper) total domination and minimum degree
• On a conjecture of \textit{TxGraffiti}: relating zero forcing and vertex covers in graphs
• Bounds for zero forcing numbers of connected graphs with fixed order and maximum degree
• Exploring the influence of graph operations on zero forcing sets
• Spectral bounds for the zero forcing number of a graph
• The conversion set problem on graphs

This page was built for publication: Dynamic approach to k-forcing

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