Truncated metric dimension for finite graphs
Truncated metric dimension for finite graphs
复制标题
有限图的截断公制维度
DOI：
10.1016/j.dam.2022.04.021
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Yi, Eunjeong
中科院分区：
文献类型：
--
作者：
Frongillo, Rafael M.;Geneson, Jesse;Lladser, Manuel E.;Tillquist, Richard C.;Yi, Eunjeong
设G是一个顶点集为V（G）的图，d（x，y）表示G中结点x和y之间的最短路的长度.对于正整数k且对于不同的x，y∈ V（G），令d k（x，y）= min {d（x，y），k+ 1}且R k {x，y}={z∈ V（G）：d k（x，z）≠ d k（y，z）}。一个子集S ∈ V（G）是G的一个k-截断可解集，如果|S R k {x，y}| ≥ 1，对任意一对不同的x，y∈ V（G）. G的k-截尾度量维数dim k（G）是G的所有k-截尾可解集上的最小基数，当k+ 1至少为G的直径时，恢复到通常的度量维数。我们得到了k-截尾度量维数的一些一般界。对所有k≥ 1，我们刻画了dim k（G）= n− 2和dim k（G）= n− 1的n阶连通图G.对任意的j，k≥ 1，我们求出了满足dim k（G）= j的图G的最大可能的阶、度、团数和色数.当G是圈或路时，我们确定了dim k（G）.我们还研究了顶点或边删除对图的截断度量维数的影响，以及与树的截断度量维数有关的各种问题.
Let G be a graph with vertex set V (G), and let d (x, y) denote the length of a shortest path between nodes x and y in G. For a positive integer k and for distinct x, y∈ V (G), let d k (x, y)= min {d (x, y), k+ 1} and R k {x, y}={z∈ V (G): d k (x, z)≠ d k (y, z)}. A subset S⊆ V (G) is a k-truncated resolving set of G if| S∩ R k {x, y}|≥ 1 for any pair of distinct x, y∈ V (G). The k-truncated metric dimension, dim k (G), of G is the minimum cardinality over all k-truncated resolving sets of G, and the usual metric dimension is recovered when k+ 1 is at least the diameter of G. We obtain some general bounds for k-truncated metric dimension. For all k≥ 1, we characterize connected graphs G of order n with dim k (G)= n− 2 and dim k (G)= n− 1. For all j, k≥ 1, we find the maximum possible order, degree, clique number, and chromatic number of any graph G with dim k (G)= j. We determine dim k (G) when G is a cycle or a path. We also examine the effect of vertex or edge deletion on the truncated metric dimension of graphs, and study various problems related to the truncated metric dimension of trees.
登录
查看更多内容
影响因子：
1.1
作者：
Fernau, Henning;Rodriguez-Velazquez, Juan A.
通讯作者：
Rodriguez-Velazquez, Juan A.
DOI：
--
发表时间：
2002
期刊：
影响因子：
--
作者：
C. Poisson;Ping Zhang
通讯作者：
Ping Zhang
DOI：
10.4310/joc.2015.v6.n4.a2
发表时间：
2015
期刊：
The Journal of Combinatorics
影响因子：
--
作者：
Linda Eroh;P. Feit;Cong X. Kang;Eunjeong Yi
通讯作者：
Eunjeong Yi
图表中的度量维度和模式避免
影响因子：
1.1
作者：
Jesse T. Geneson
通讯作者：
Jesse T. Geneson
DOI：
--
发表时间：
2021
期刊：
影响因子：
--
作者：
Jesse T. Geneson;Eunjeong Yi
通讯作者：
Eunjeong Yi