平面图Γn的边度量维数研究

康娜　李志全　杨丽婷

【摘   要】   圖的度量维数是图论与组合优化交叉领域的重要研究内容，边度量维数是度量维数的一个变形。 给出了平面图Γ_n的一个边度量生成集，并证明了当n≥6时，平面图Γ_n的边度量维数为3。

【关键词】   边度量维数;边度量生成集;平面图Γ_n

Study on the Edge Metric Dimension of Plane Graph Γ_n

Kang Na， Li Zhiquan， Yang Liting

（Hebei GEO University， Shijiazhuang 050031， China）

【Abstract】    The metric dimension of graph is an important object in the intersection between graph theory and combinatorial optimization. The edge metric dimension is a variation of metric dimension of graph. This paper presentsan edge metric generator of plane graph Γ_n， and shows that the edge metric dimension of Γ_nis 3 when n≥6.

【Key words】     edge metric dimension; edge metric generator; plane graphΓ_n

〔中图分类号〕  O157.5             〔文献标识码〕  A              〔文章编号〕 1674 - 3229（2022）02- 0005 - 03

0      引言

1953年，Blumenthal[1]引入了一般度量空间中度量维数的概念。Slater[2]以及Harary和Melter[3]分别于1975年和1976年独立地把解析集和度量维数的概念引入到图中。图的度量维数在医药化学[4]、机器巡航[5]等领域都有广泛的应用。目前图的度量维数的研究已取得许多成果[6-9]。

设G是一个有限无向简单的连通图，其中V（G）为顶点集，E（G）为边集。图G中两顶点u、v之间的距离d（u，v）是以u和v为端点的最短路中所有边的条数。对于顶点x∈V（G），若d（x，u）≠d（x，v），则称顶点x解析顶点u、v。设S是图G中一个非空的顶点子集，如果G中的任意两个顶点都能被S中的某个顶点解析，称S是图G的解析集。图G的基数最小的解析集称作图G的度量基，其基数称作图G的度量维数，记作dim（G）。

2018年，Kelenc[10]等人将度量维数进行了变形，给出了图的边度量维数的概念。此后，图的边度量维数问题引起了许多学者的关注[11-16]。

1     主要结论

2     结语

图的度量维数是图论与组合优化交叉领域的重要内容。本文给出了平面图Γ_n的一个边度量生成集，并证明了当n≥6时，平面图Γ_n的边度量维数为3。本文研究对度量维数的研究与发展有积极的推动作用。关于该平面图的混合度量维数尚无结论，后续将进一步研究平面图Γ_n的混合度量维数及其他一些平面图的（点、边、混合）度量维数。

[参考文献]

[1]  Blumenthal L M. Theory and applications of distance geometry[M]. Oxford：Clarendon Press， 1953.

[2] Slater P J. Leaves of trees[J]. Proceeding of the 6th Southeastern Conference on Combinatorics， Graph Theory， and Computing， Congressus Numerantium， 1975， 14： 549-559.

[3] Harary F， Melter R A. On the metric dimension of a graph  [J]. Ars Combinatorial， 1976 （2）： 191-195.

[4] Chartrand G， Eroh L， Johnson M A， et al. Resolvability in graphs and the metric  dimension of a graph[J]. Discrete Applied Mathematics， 2000， 105 （1-3）： 99-113.

[5]Khuller S， Raghavachari B， Rosenfeld A. Landmarks in graphs[J]. Discrete Applied Mathematics， 1996， 70 （3）： 217-229.CB01F5E6-8224-48DA-B2C0-8B4DC33D85A2

[6] Cáceres J， Hernando C， Mora M， et al. On the metric dimension of Cartesian products of graphs[J]. SIAM Journal on Discrete Mathematics， 2007， 21（2）： 423-441.

[7] Imran M， Baig A Q， Bokhary S A. On the metric dimension of rotationally-symmetric graphs[J]. Ars Combinatorial， 2016， 124： 111-128.

[8]  Zhang Y Z， Hou L H， Wu W L， et al. On the metric dimension of the folded  -cube [J]. Optimization. Letters， 2020， 14（1）： 249-257.

[9] Guo J， Wang K S， Li F G. Metric dimension of some distance-regular graphs[J]. Jouranl of Combinatorial Optimization， 2013， 26（1）： 190-197.

[10] Kelenc A， Tratnik N， Yero I G. Uniquely identifying the edge of a graph： the edge metric dimension[J]. Discrete Applied Mathematics， 2018， 251： 204-220.

[11] Nasir R， Zafar S， Zahid Z. Edge metric dimension of graphs[J]. Ars Combinatorial， 2018， 147： 143-156.

[12] Adawiyah R， Dafik， Alfarisi R， et al. Edge metric dimension on some families of tree[C]. Journal of Physics：Conference Series， 2019.

[13] Zhang Y Z， Gao S G. On the edge metric dimension of convex polytopes and its related graphs Journal of Combinatorial Optimization[J]. Jouranl of Combinatorial Optimization， 2020， 39（2）： 334-350.

[14] Zubrilina N. On the edge dimension of a graph[J]. Discrete Mathematics， 2018， 341（7）： 2083-2088.

[15] Kratica J， Filipovic V， Kartelj A. Edge metric dimension of some generalized petersen graphs[J]. Results in Mathematics， 2019， 74（4）： 1-15.

[16] 張跃忠.关于图的度量维数及其相对设计的研究[D].石家庄：河北师范大学， 2020.

[17] Khuller S， Raghavachari B， Rosenfeld A. Landmarks in graphs[J]. Discrete Applied Mathematics， 1996， 70 （3）： 217-229.CB01F5E6-8224-48DA-B2C0-8B4DC33D85A2