平面圖Γn的邊度量維數(shù)研究

康娜　李志全　楊麗婷

【摘? ?要】? ?圖的度量維數(shù)是圖論與組合優(yōu)化交叉領(lǐng)域的重要研究內(nèi)容，邊度量維數(shù)是度量維數(shù)的一個變形。 給出了平面圖Γ_n的一個邊度量生成集，并證明了當(dāng)n≥6時，平面圖Γ_n的邊度量維數(shù)為3。

【關(guān)鍵詞】? ?邊度量維數(shù);邊度量生成集;平面圖Γ_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? ? ? ? ? ? ?〔文獻標(biāo)識碼〕? A ? ? ? ? ? ? ?〔文章編號〕 1674 - 3229（2022）02- 0005 - 03

0? ? ? 引言

1953年，Blumenthal[1]引入了一般度量空間中度量維數(shù)的概念。Slater[2]以及Harary和Melter[3]分別于1975年和1976年獨立地把解析集和度量維數(shù)的概念引入到圖中。圖的度量維數(shù)在醫(yī)藥化學(xué)[4]、機器巡航[5]等領(lǐng)域都有廣泛的應(yīng)用。目前圖的度量維數(shù)的研究已取得許多成果[6-9]。

設(shè)G是一個有限無向簡單的連通圖，其中V（G）為頂點集，E（G）為邊集。圖G中兩頂點u、v之間的距離d（u，v）是以u和v為端點的最短路中所有邊的條數(shù)。對于頂點x∈V（G），若d（x，u）≠d（x，v），則稱頂點x解析頂點u、v。設(shè)S是圖G中一個非空的頂點子集，如果G中的任意兩個頂點都能被S中的某個頂點解析，稱S是圖G的解析集。圖G的基數(shù)最小的解析集稱作圖G的度量基，其基數(shù)稱作圖G的度量維數(shù)，記作dim（G）。

2018年，Kelenc[10]等人將度量維數(shù)進行了變形，給出了圖的邊度量維數(shù)的概念。此后，圖的邊度量維數(shù)問題引起了許多學(xué)者的關(guān)注[11-16]。

1? ? ?主要結(jié)論

2? ? ?結(jié)語

圖的度量維數(shù)是圖論與組合優(yōu)化交叉領(lǐng)域的重要內(nèi)容。本文給出了平面圖Γ_n的一個邊度量生成集，并證明了當(dāng)n≥6時，平面圖Γ_n的邊度量維數(shù)為3。本文研究對度量維數(shù)的研究與發(fā)展有積極的推動作用。關(guān)于該平面圖的混合度量維數(shù)尚無結(jié)論，后續(xù)將進一步研究平面圖Γ_n的混合度量維數(shù)及其他一些平面圖的（點、邊、混合）度量維數(shù)。

[參考文獻]

[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] 張躍忠.關(guān)于圖的度量維數(shù)及其相對設(shè)計的研究[D].石家莊：河北師范大學(xué)， 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