Characterizing 1-metric antidimensional trees and unicyclic graphs
Trujillo Rasua, Rolando and Yero, Ismael G 2016, Characterizing 1-metric antidimensional trees and unicyclic graphs, Computer journal, vol. 59, no. 8, pp. 1264-1273, doi: 10.1093/comjnl/bxw021.
Attached Files
Name
Description
MIMEType
Size
Downloads
Title
Characterizing 1-metric antidimensional trees and unicyclic graphs
Let G=(V,E) be a simple connected graph and S={w1, wt} V an ordered subset of vertices. The metric representation of a vertex u V with respect to S is the t-vector r(u|S)=(dG(u,w1), dG(u,wt)), where dG(u,v) represents the length of a shortest u-v path in G. A set S is a k-antiresolving set if k is the largest positive integer such that for every vertex v V-S there exist other k-1 different vertices v1, vk-1 V-S such that v,v1, vk-1 have the same metric representation with respect to S. The k-metric antidimension of G is the minimum cardinality among all the k-antiresolving sets for G, and G is k-metric antidimensional if k is the largest integer such that G contains a k-antiresolving set. In this article, we provide characterizations for 1-metric antidimensional trees and unicyclic graphs, together with computationally efficient algorithms to decide whether these types of graphs are 1-metric antidimensional.
Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.