A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
复制标题
DOI：
10.1007/s10114-017-4699-4
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Linda Eroh;Cong X. Kang;Eunjeong Yi
中科院分区：
文献类型：
--
作者：
Linda Eroh;Cong X. Kang;Eunjeong Yi
图G的度量维数dim（G）是使G的每一个顶点都由它到所选顶点的距离向量唯一确定的最小顶点数。图G的迫零数Z（G）是一组黑色顶点S（而V（G）萨雷中的顶点被着色为白色）的最小基数，使得V（G）在多次应用“颜色变化规则”后变为黑色：如果一个白色顶点是一个黑色顶点的唯一白色邻居，则该白色顶点变为黑色。本文证明了树T的dim（T）≤Z（T），如果G是单圈图，则dim（G）≤Z（G）+1;沿着这条路，我们刻画了树T达到dim（T）=Z（T）.对于一般图G，我们引入了“圈秩猜想”。最后，我们证明了dim（T）− 2 ≤ dim（T+e）≤ dim（T）+ 1。
Themetric dimensiondim(G) of a graphGis the minimum number of vertices such that every vertex ofGis uniquely determined by its vector of distances to the chosen vertices. Thezero forcing number Z(G) of a graphGis the minimum cardinality of a setSof black vertices (whereas vertices inV(G)Sare colored white) such thatV(G) is turned black after finitely many applications of “the color-change rule”: a white vertex is converted black if it is the only white neighbor of a black vertex. We show that dim(T) ≤Z(T) for a treeT, and that dim(G) ≤Z(G)+1 ifGis a unicyclic graph; along the way, we characterize treesTattaining dim(T) =Z(T). For a general graphG, we introduce the “cycle rank conjecture”. We conclude with a proof of dim(T) − 2 ≤ dim(T+e) ≤ dim(T) + 1 for.