Uniform forcing and immune sets in graphs and hypergraphs

DOI10.1016/J.DAM.2021.08.019MaRDI QIDQ2235248zbMATH OpenOpenAlexFDO

Authors J. Fàbrega, Jaume Martí-Farré, Xavier Muñoz

Publication date 21 October 2021

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

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

zbMATH Keywords

hypergraphspropagation in networkszero forcing

Mathematics Subject Classification ID

Hypergraphs (05C65) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: Zero forcing is an iterative coloring process on a graph that has been widely used in such different areas as the modelling of propagation phenomena in networks and the study of minimum rank problems in matrices and graphs. This paper deals with zero forcing on hypergraphs. (Representing a network by a hypergraph allows us to account for its community structure and for more general interactions between different subsets of nodes.) We consider two natural generalizations to hypergraphs of zero forcing on graphs (one of them already known) and, for each one of these generalizations we look into two clutters that play a significant role in the forcing process: the clutter of minimal forcing sets and the one of minimal immune sets. A formulation of immune sets in terms of neighbourhoods (hence without making reference to the iterative zero forcing process) is presented, highlighting the different behaviour of the distinct forcing rules. Moreover, we obtain the families of minimal forcing and minimal immune sets in the case of complete hypergraphs and we provide a full characterization of forcing and immune uniform clutters, both in the graph and in the hypergraph case.

Recommendations

• Zero forcing and maximum nullity for hypergraphs
• On trees and unicyclic graphs with equal forcing-type numbers
• Some algebraic hyperstructures related to zero forcing sets and forcing digraphs
• The Zero Forcing Number of Graphs
• Zero-forcing in random regular graphs

Cites work

• Dynamical Processes on Complex Networks
• Effects of vertex degrees on the zero-forcing number and propagation time of a graph
• Extremal combinatorics. With applications in computer science
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• Infection in hypergraphs
• On infection in hypergraphs
• SIS epidemic propagation on hypergraphs
• The minimum rank of symmetric matrices described by a graph: a survey
• The Zero Forcing Number of Graphs
• Zero forcing and maximum nullity for hypergraphs
• Zero forcing sets and the minimum rank of graphs

Cited in

(4)

• Zero forcing and maximum nullity for hypergraphs
• On infection in hypergraphs
• Immune sets in monotone infection rules. Characterization and complexity
• On the size of immune sets in the k-PULL infection model

This page was built for publication: Uniform forcing and immune sets in graphs and hypergraphs

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