Isomorphisms and properties of TAR reconfiguration graphs for zero forcing and other $X$-set parameters
Isomorphisms and properties of TAR reconfiguration graphs for zero forcing and other $X$-set parameters
复制标题
迫零和其他 $X$ 集参数的 TAR 重配置图的同构和属性
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
L. Hogben
中科院分区：
文献类型：
--
作者：
N. H. Bong;Joshua Carlson;Bryan A. Curtis;R. Haas;L. Hogben
X-TAR（令牌添加/删除）重新配置图具有满足某些属性 X 的顶点集，如果通过添加或删除一个元素从另一个集合获得一个集合，则两个集合之间有一条边。本文考虑基本图 G 的 X - 顶点集的 X -TAR 图，其中 G 的 X - 集必须满足某些条件。支配集、幂支配集、迫零集和正半定迫零集都是 X 集的例子。对于没有孤立顶点的图 G 和 G ′，当且仅当对 G ′ 的顶点进行重新标记使得 G 和 G ′ 具有完全相同的 X 集时，G 和 G ′ 具有同构 X -TAR 重配置图。引入X无关顶点的概念是为了方便X-TAR图同构的分析。此外，还给出了与迫零 TAR 图连通性相关的结果。我们提出了超出已知连通性参数下限的图族。
An X -TAR (token addition/removal) reconfiguration graph has as its vertices sets that satisfy some property X , with an edge between two sets if one is obtained from the other by adding or removing one element. This paper considers the X -TAR graph for X − sets of vertices of a base graph G where the X -sets of G must satisfy certain conditions. Dominating sets, power dominating sets, zero forcing sets, and positive semidefinite zero forcing sets are all examples of X -sets. For graphs G and G ′ with no isolated vertices, it is shown that G and G ′ have isomorphic X -TAR reconfiguration graphs if and only if there is a relabeling of the vertices of G ′ such that G and G ′ have exactly the same X -sets. The concept of an X -irrelevant vertex is introduced to facilitate analysis of X -TAR graph isomorphisms. Furthermore, results related to the connectedness of the zero forcing TAR graph are given. We present families of graphs that exceed known lower bounds for connectedness parameters.