Fractional zero forcing via three-color forcing games

DOI10.1016/J.DAM.2016.05.004MaRDI QIDQ313806zbMATH OpenOpenAlexFDO

Authors Leslie Hogben, Kevin F. Palmowski, David Roberson, Michael Young

Publication date 12 September 2016

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

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

zbMATH Keywords

fractionalpositive semidefiniteskewzero forcing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Games involving graphs (91A43)

Abstract: An $r$-fold analogue of the positive semidefinite zero forcing process that is carried out on the $r$-blowup of a graph is introduced and used to define the fractional positive semidefinite forcing number. Properties of the graph blowup when colored with a fractional positive semidefinite forcing set are examined and used to define a three-color forcing game that directly computes the fractional positive semidefinite forcing number of a graph. We develop a fractional parameter based on the standard zero forcing process and it is shown that this parameter is exactly the skew zero forcing number with a three-color approach. This approach and an algorithm are used to characterize graphs whose skew zero forcing number equals zero.

Recommendations

• Skew throttling
• Failed skew zero forcing on a graph
• Three-state zero forcing on graphs
• Throttling for zero forcing and variants
• Probalistic zero forcing in graphs

Cites work

• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• Minimum rank of skew-symmetric matrices described by a graph
• Minimum rank with zero diagonal
• Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Positive semidefinite maximum nullity and zero forcing number
• Positive semidefinite propagation time
• Propagation time for zero forcing on a graph
• Upper bounds on the \(k\)-forcing number of a graph
• Zero Forcing, Linear and Quantum Controllability for Systems Evolving on Networks
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(7)

• Zero forcing and maximum nullity for hypergraphs
• The zero forcing polynomial of a graph
• Properties of a \(q\)-analogue of zero forcing
• Computational approaches for zero forcing and related problems
• Complexity and computation of connected zero forcing
• The \(q\)-analogue of zero forcing for certain families of graphs
• Zero forcing propagation time on oriented graphs

This page was built for publication: Fractional zero forcing via three-color forcing games

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