On the relationships between zero forcing numbers and certain graph coverings

DOI10.2478/SPMA-2014-0004zbMATH Open1291.05126OpenAlexW2067092314MaRDI QIDQ2017194FDOQ2017194

Authors Fatemeh Alinaghipour Taklimi, K. Meagher, Shaun M. Fallat 

Publication date 25 June 2014

Published in Special Matrices (Search for Journal in Brave)

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

zbMATH Keywords

zero forcing numberpath cover numbertree cover numberpositive zero forcing number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Sign pattern matrices (15B35)

Abstract: The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph. We show that for a block-cycle graph the zero forcing number equals the path cover number. We also give a purely graph theoretical proof that the positive zero forcing number of any outerplanar graphs equals the tree cover number of the graph. These ideas are then extended to the setting of $k$-trees, where the relationship between the positive zero forcing number and the tree cover number becomes more complex.

Recommendations

• On the relationship between the zero forcing number and path cover number for some graphs
• Zero forcing number, path cover number, and maximum nullity of cacti
• Positive zero forcing and edge clique coverings
• Computing the zero forcing number for generalized Petersen graphs
• Zero forcing parameters and minimum rank problems

Cites Work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A technique for computing the zero forcing number of a graph with a cut-vertex
• Fast-mixed searching and related problems on graphs
• Linearly independent vertices and minimum semidefinite rank
• Minimum rank, maximum nullity and zero forcing number for selected graph families
• Minimum semidefinite rank of outerplanar graphs and the tree cover number
• Nondiscriminatory propagation on trees
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
• On minimum rank and zero forcing sets of a graph
• On the difference between the maximum multiplicity and path cover number for tree-like graphs
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Positive semidefinite zero forcing
• The graphs for which the maximum multiplicity of an eigenvalue is two
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Zero Forcing, Linear and Quantum Controllability for Systems Evolving on Networks
• Zero forcing number, path cover number, and maximum nullity of cacti
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited In (12)

• Vector representations of graphs and distinguishing quantum product states with one-way LOCC
• Positive zero forcing and edge clique coverings
• Grundy domination and zero forcing in regular graphs
• Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters
• Effects of vertex degrees on the zero-forcing number and propagation time of a graph
• Proof of a conjecture on the zero forcing number of a graph
• Some algebraic hyperstructures related to zero forcing sets and forcing digraphs
• The zero (total) forcing number and covering number of trees
• Compressed cliques graphs, clique coverings and positive zero forcing
• Zero forcing sets and bipartite circulants
• On the relationship between the zero forcing number and path cover number for some graphs
• Grundy dominating sequences and zero forcing sets

This page was built for publication: On the relationships between zero forcing numbers and certain graph coverings

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