On the relationships between zero forcing numbers and certain graph coverings

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

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

Publication date: 25 June 2014

Published in: Special Matrices (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Zero forcing sets and the minimum rank of graphs
• Title not available (Why is that?)
• 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
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• On minimum rank and zero forcing sets of a graph
• Zero forcing parameters and minimum rank problems
• Positive semidefinite zero forcing
• Nondiscriminatory propagation on trees
• A technique for computing the zero forcing number of a graph with a cut-vertex
• Zero Forcing, Linear and Quantum Controllability for Systems Evolving on Networks
• Linearly independent vertices and minimum semidefinite rank
• Fast-mixed searching and related problems on graphs
• On the difference between the maximum multiplicity and path cover number for tree-like graphs
• Minimum semidefinite rank of outerplanar graphs and the tree cover number
• Minimum rank, maximum nullity and zero forcing number for selected graph families
• Zero forcing number, path cover number, and maximum nullity of cacti
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees

Cited In (9)

• Vector representations of graphs and distinguishing quantum product states with one-way LOCC
• 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
• 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)