TY - JOUR
T1 - Resolvability and fault-tolerant resolvability structures of convex polytopes
AU - Siddiqui, Hafiz Muhammad Afzal
AU - Hayat, Sakander
AU - Khan, Asad
AU - Imran, Muhammad
AU - Razzaq, Ayesha
AU - Liu, Jia Bao
N1 - Funding Information:
J.-B. Liu is partially supported by National Natural Science Foundation of China via grant No. 11601006 . S. Hayat is supported by the Startup Research Grant Program of Higher Education Commission ( HEC ) Pakistan under Project# 2285 and grant No. 21-2285/SRGP/R&D/HEC/2018 . M. Imran is supported by the Start-up Research Grant 2016 of United Arab Emirates University , Al Ain, United Arab Emirates via Grant No. G00002233 and UPAR Grant of United Arab Emirates University via grant No. G00002590 . The authors would like to thank the anonymous reviewer for a careful reading of this article and for all of his/her comments, which lead to a number of improvements of the article.
Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2019/12/3
Y1 - 2019/12/3
N2 - In this paper, we study resolvability and fault-tolerant resolvability of convex polytopes and related geometric graphs. Imran et al. (2010) [18] raised an open problem asserting that whether or not every family of convex polytope has a constant metric dimension. Raza et al. (2018) [28] studied the fault-tolerant metric dimension of certain families of convex polytopes. They also concluded their study with an open problem asking whether or not every family of convex polytope has a constant fault-tolerant metric dimension. In this paper, we provide negative answers to both of the aforementioned open problems. We answer the first question by constructing a family of convex polytopes with an unbounded metric dimension. By proving a result between resolvability and fault-tolerant resolvability structures of a graph, we show that the family of convex polytope with an unbounded metric dimension also possesses an unbounded fault-tolerant resolvability structure. Moreover, we construct three more infinite families of graphs which are closely related to convex polytopes, having an unbounded metric dimension.
AB - In this paper, we study resolvability and fault-tolerant resolvability of convex polytopes and related geometric graphs. Imran et al. (2010) [18] raised an open problem asserting that whether or not every family of convex polytope has a constant metric dimension. Raza et al. (2018) [28] studied the fault-tolerant metric dimension of certain families of convex polytopes. They also concluded their study with an open problem asking whether or not every family of convex polytope has a constant fault-tolerant metric dimension. In this paper, we provide negative answers to both of the aforementioned open problems. We answer the first question by constructing a family of convex polytopes with an unbounded metric dimension. By proving a result between resolvability and fault-tolerant resolvability structures of a graph, we show that the family of convex polytope with an unbounded metric dimension also possesses an unbounded fault-tolerant resolvability structure. Moreover, we construct three more infinite families of graphs which are closely related to convex polytopes, having an unbounded metric dimension.
KW - Convex polytopes
KW - Fault-tolerant metric dimension
KW - Geometric graphs
KW - Metric dimension
KW - NP-complete problems
UR - http://www.scopus.com/inward/record.url?scp=85071663013&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85071663013&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2019.08.032
DO - 10.1016/j.tcs.2019.08.032
M3 - Article
AN - SCOPUS:85071663013
SN - 0304-3975
VL - 796
SP - 114
EP - 128
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -