Failed Skew Zero Forcing Numbers of Path Powers and Circulant Graphs
Open Access
- 24 March 2025
- journal article
- research article
- Published by MDPI AG in AppliedMath
- Vol. 5 (2) , 32
Abstract
For a graph G, the zero forcing number of G, , is defined to be the minimum cardinality of a set S of vertices for which repeated applications of the forcing rule results in all vertices being in S. The forcing rule is as follows: if a vertex v is in S, and exactly one neighbor u of v is not in S, then the vertex u is added to S in the subsequent iteration. Now, the failed zero forcing number of a graph is defined to be the maximum size of a set of vertices which does not force all of the vertices in the graph. A similar type of forcing is called skew zero forcing, which is defined so that if there is exactly one neighbor u of v that is not in S, then the vertex u is added to S in the next iteration. The key difference is that vertices that are not in S can force other vertices. The failed skew zero forcing number of a graph is denoted by . At its core, the problem we consider is how to identify the tipping point at which information or infection will spread through a network or a population. The graphs we consider are where computers/routers or people are arranged in a linear or circular formation with varying proximities for contagion. Here, we present new results for failed skew zero forcing numbers of path powers and circulant graphs. Furthermore, we found that the failed skew zero forcing numbers of these families form interesting sequences with increasing n.
Keywords
Funding Information
- National Science Foundation (1950189)
This publication has 14 references indexed in Scilit:
- Parallel Generation and Analysis of Optimal Chordal Ring Networks Using Python Tools on Kunpeng Processors2023
- On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free RoutingAlgorithms, 2022
- Routing Algorithms in Optimal Degree Four Circulant Networks Based on Relative Addressing: Comparative Analysis for Networks-on-ChipIEEE Transactions on Network Science and Engineering, 2022
- Blocking zero forcing processes in Cartesian products of graphsDiscrete Applied Mathematics, 2020
- On the zero blocking number of rectangular, cylindrical, and Möbius gridsDiscrete Applied Mathematics, 2020
- On the complexity of failed zero forcingTheoretical Computer Science, 2017
- Failed skew zero forcing on a graphLinear Algebra and its Applications, 2016
- The failed zero forcing number of a graphInvolve, a Journal of Mathematics, 2015
- The minimum rank of symmetric matrices described by a graph: A surveyLinear Algebra and its Applications, 2007
- Collective dynamics of ‘small-world’ networksNature, 1998