The q-analogue of zero forcing for certain families of graphs
The q-analogue of zero forcing for certain families of graphs
复制标题
DOI：
10.1016/j.dam.2024.01.014
复制
发表时间：
2024-05
影响因子：
1.1
通讯作者：
Shaun M. Fallat;N. Joshi;Roghayeh Maleki;Karen Meagher;S. A. Mojallal;S. Nasserasr;M. N. Shirazi;A. S. Razafimahatratra;B. Stevens
中科院分区：
文献类型：
--
作者：
Shaun M. Fallat;N. Joshi;Roghayeh Maleki;Karen Meagher;S. A. Mojallal;S. Nasserasr;M. N. Shirazi;A. S. Razafimahatratra;B. Stevens
迫零是一种在图上进行的组合游戏，其最终目标是以最小的代价改变所有顶点的颜色。最初这个游戏被认为是一个玩家的游戏，但后来一个两个玩家的版本被设计出来，结合对图的惯性的研究，并被称为零强迫的q模拟。本文研究并计算了各种图族的q-模拟迫零数。我们开始考虑与树有关的收缩概念。然后，我们显着推广这个q模拟迫零和相应的零参数之间的方程的所有阈值图。最后，我们研究了某些Kneser图的迫零的q-模拟，以及结构图的各种Carnival乘积。
Zero forcing is a combinatorial game played on a graph with the ultimate goal of changing the colour of all the vertices at minimal cost. Originally this game was conceived as a one player game, but later a two-player version was devised in-conjunction with studies on the inertia of a graph, and has become known as the q-analogue of zero forcing. In this paper, we study and compute the q-analogue zero forcing number for various families of graphs. We begin with by considering a concept of contraction associated with trees. We then significantly generalize an equation between this q-analogue of zero forcing and a corresponding nullity parameter for all threshold graphs. We close by studying the q-analogue of zero forcing for certain Kneser graphs, and a variety of cartesian products of structured graphs.