康娜　李志全　楊麗婷

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

〔中圖分類(lèi)號(hào)〕? O157.5? ? ? ? ? ? ?〔文獻(xiàn)標(biāo)識(shí)碼〕? A ? ? ? ? ? ? ?〔文章編號(hào)〕 1674 - 3229（2022）02- 0005 - 03

0? ? ? 引言

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

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

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

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

2? ? ?結(jié)語(yǔ)

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

[參考文獻(xià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] 張躍忠.關(guān)于圖的度量維數(shù)及其相對(duì)設(shè)計(jì)的研究[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