Bounds for the Zero Forcing Number of Graphs with Large Girth

DOI10.20429/TAG.2015.020201MaRDI QIDQ5225511zbMATH OpenOpenAlexFDO

Authors Randy Davila, Franklin Kenter

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/1406.0482

zbMATH Keywords

maximum nullity of all symmetric matrices with a sparsity pattern

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: We investigate the zero-forcing number for triangle-free graphs. We improve upon the trivial bound, $deltaleZ(G)$ where $delta$ is the minimum degree, in the triangle-free case. In particular, we show that $2delta-2leZ(G)$ for graphs with girth of at least 5, and this can be further improved when $G$ has a small cut set. Using these results, we are able to prove the Graph Complement Conjecture on minimum rank for a large class of graphs. Lastly, we make a conjecture that the lower bound for $Z(G)$ increases as a function of the girth, $g$, and $delta$.

Recommendations

• Some bounds on the zero forcing number of a graph
• A short proof for a lower bound on the zero forcing number
• A lower bound on the zero forcing number
• On extremal graphs for zero forcing number
• On graphs maximizing the zero forcing number

Cited in

(38)

• Some bounds on the zero forcing number of a graph
• On a conjecture of Gentner and Rautenbach
• On the total forcing number of a graph
• Bounds on the connected forcing number of a graph
• Total forcing and zero forcing in claw-free cubic graphs
• A lower bound on the zero forcing number
• Total forcing versus total domination in cubic graphs
• Complexity and computation of connected zero forcing
• Zero forcing versus domination in cubic graphs
• Tight bounds on probabilistic zero forcing on hypercubes and grids
• On extremal graphs for zero forcing number
• On the zero forcing number and spectral radius of graphs
• Total forcing sets and zero forcing sets in trees
• Probabilistic zero forcing on random graphs
• A short proof for a lower bound on the zero forcing number
• 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
• Maximum nullity and zero forcing of circulant graphs
• Proof of a conjecture on the zero forcing number of a graph
• Extremal values and bounds for the zero forcing number
• The Zero Forcing Number of Graphs
• The forcing number of graphs with given girth
• Edge forcing in butterfly networks
• Propagation time for probabilistic zero forcing
• Matching, path covers, and total forcing sets
• UPPER BOUNDS ON THE SEMITOTAL FORCING NUMBER OF GRAPHS
• On graphs maximizing the zero forcing number
• The zero forcing number of graphs with the matching number and the cyclomatic number
• Maximum nullity, zero forcing number and propagation time of -path graphs
• Bounding the total forcing number of graphs
• The zero (total) forcing number and covering number of trees
• Zero forcing number and propagation time discrepancy of some graphs
• Zero forcing number and maximum nullity of general power graphs
• Propagating sets in Sierpiński fractal graphs
• Some results on the total (zero) forcing number of a graph
• On the zero forcing number of trees
• The zero forcing number of expanded paths and cycles

This page was built for publication: Bounds for the Zero Forcing Number of Graphs with Large Girth

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