Zero forcing and maximum nullity for hypergraphs

DOI10.1016/J.DAM.2019.11.019MaRDI QIDQ2185737zbMATH OpenOpenAlexFDO

Authors Leslie Hogben

Publication date 5 June 2020

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

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

zbMATH Keywords

hypergraphhypermatrixinfection numbermaximum nullitypower dominationzero forcing

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The concept of zero forcing is extended from graphs to uniform hypergraphs in analogy with the way zero forcing was defined as an upper bound for the maximum nullity of the family of symmetric matrices whose nonzero pattern of entries is described by a given graph: A family of symmetric hypermatrices is associated with a uniform hypergraph and zeros are forced in a null vector. The value of the hypergraph zero forcing number and maximum nullity are determined for various families of uniform hypergraphs and the effects of several graph operations on the hypergraph zero forcing number are determined. The hypergraph zero forcing number is compared to the infection number of a hypergraph and the iteration process in hypergraph power domination.

Review text

The concept of zero forcing and of (maximum) nullity is well-known in the context of graphs. It is defined using the adjacency matrix of a graph, a very natural and well-known construction. The author generalizes these notions to (uniform) hypergraphs and uses hypercubical hypermatrices for this purpose -- a construction that generalizes adjacency matrices. After introducing zero forcing and maximum nullity for uniform hypergraphs, the author shows that the former is an upper bound for the latter. Further results compare these new concepts to the infection number of a hypergraph and the iteration process in hypergraph dominations.

Recommendations

• Uniform forcing and immune sets in graphs and hypergraphs
• Positive semidefinite maximum nullity and zero forcing number
• On infection in hypergraphs
• Zero forcing for sign patterns
• Infection in hypergraphs

Cites work

• Domination in Graphs Applied to Electric Power Networks
• Fractional zero forcing via three-color forcing games
• Hypergraph theory. An introduction
• Infection in hypergraphs
• Minimum rank of skew-symmetric matrices described by a graph
• Minimum rank with zero diagonal
• On the \({k}\)-power domination of hypergraphs
• The minimum rank of symmetric matrices described by a graph: a survey
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Zero forcing and power domination for graph products
• Zero forcing sets and the minimum rank of graphs

Cited in

(11)

• Zero forcing in iterated line digraphs
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• Rigid linkages and partial zero forcing
• From the editor-in-chief
• Uniform forcing and immune sets in graphs and hypergraphs
• Infectious power domination of hypergraphs
• Geometric vs algebraic nullity for hyperpaths
• Probabilistic Zero Forcing on Grid, Regular, and Hypercube Graphs
• Some algebraic hyperstructures related to zero forcing sets and forcing digraphs
• On infection in hypergraphs
• On the zero forcing number of the complement of graphs with forbidden subgraphs

This page was built for publication: Zero forcing and maximum nullity for hypergraphs

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