Determining the edge metric dimension of the generalized Petersen graph P(n, 3)

David G.L. Wang; Monica M.Y. Wang; Shiqiang Zhang

doi:10.1007/s10878-021-00780-8

Determining the edge metric dimension of the generalized Petersen graph P(n, 3)

David G.L. Wang^*
, Monica M.Y. Wang
, Shiqiang Zhang

^*此作品的通讯作者

数学学院

Ministry of Industry and Information Technology
Beijing Institute of Technology
Imperial College London

科研成果: 期刊稿件 › 文章 › 同行评审

8 引用（Scopus）

摘要

It is known that the problem of computing the edge dimension of a graph is NP-hard, and that the edge dimension of any generalized Petersen graph P(n, k) is at least 3. We prove that the graph P(n, 3) has edge dimension 4 for n≥ 11 , by showing semi-combinatorially the nonexistence of an edge resolving set of order 3 and by constructing explicitly an edge resolving set of order 4.

源语言	英语
页（从-至）	460-496
页数	37
期刊	Journal of Combinatorial Optimization
卷	43
期	2
DOI	https://doi.org/10.1007/s10878-021-00780-8
出版状态	已出版 - 3月 2022

访问文件

10.1007/s10878-021-00780-8

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{ab417d1bcaa8454686ba4b5b53c8f8e1,

title = "Determining the edge metric dimension of the generalized Petersen graph P(n, 3)",

abstract = "It is known that the problem of computing the edge dimension of a graph is NP-hard, and that the edge dimension of any generalized Petersen graph P(n, k) is at least 3. We prove that the graph P(n, 3) has edge dimension 4 for n≥ 11 , by showing semi-combinatorially the nonexistence of an edge resolving set of order 3 and by constructing explicitly an edge resolving set of order 4.",

keywords = "Floyd-Warshall algorithm, Generalized Petersen graph, Metric dimension, Resolving set",

author = "Wang, \{David G.L.\} and Wang, \{Monica M.Y.\} and Shiqiang Zhang",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2022",

month = mar,

doi = "10.1007/s10878-021-00780-8",

language = "English",

volume = "43",

pages = "460--496",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Determining the edge metric dimension of the generalized Petersen graph P(n, 3)

AU - Wang, David G.L.

AU - Wang, Monica M.Y.

AU - Zhang, Shiqiang

PY - 2022/3

Y1 - 2022/3

N2 - It is known that the problem of computing the edge dimension of a graph is NP-hard, and that the edge dimension of any generalized Petersen graph P(n, k) is at least 3. We prove that the graph P(n, 3) has edge dimension 4 for n≥ 11 , by showing semi-combinatorially the nonexistence of an edge resolving set of order 3 and by constructing explicitly an edge resolving set of order 4.

AB - It is known that the problem of computing the edge dimension of a graph is NP-hard, and that the edge dimension of any generalized Petersen graph P(n, k) is at least 3. We prove that the graph P(n, 3) has edge dimension 4 for n≥ 11 , by showing semi-combinatorially the nonexistence of an edge resolving set of order 3 and by constructing explicitly an edge resolving set of order 4.

KW - Floyd-Warshall algorithm

KW - Generalized Petersen graph

KW - Metric dimension

KW - Resolving set

UR - https://www.scopus.com/pages/publications/85111520525

U2 - 10.1007/s10878-021-00780-8

DO - 10.1007/s10878-021-00780-8

M3 - Article

AN - SCOPUS:85111520525

SN - 1382-6905

VL - 43

SP - 460

EP - 496

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -

Determining the edge metric dimension of the generalized Petersen graph P(n, 3)

摘要

访问文件

其它文件与链接

指纹

引用此