Fractional zero forcing via three-color forcing games

DOI10.1016/J.DAM.2016.05.004zbMATH Open1344.05062arXiv1509.02883OpenAlexW2206067522MaRDI QIDQ313806FDOQ313806

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)

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.

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

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

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)

Cites Work

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

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)