Characterizing 1-Metric Antidimensional Trees and Unicyclic Graphs
- 15 July 2016
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 59 (8) , 1264-1273
Abstract
Let be a simple connected graph and an ordered subset of vertices. The metric representation of a vertex with respect to S is the t -vector , where represents the length of a shortest path in G . A set S is a k -antiresolving set if k is the largest positive integer such that for every vertex there exist other different vertices such that 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.
Keywords
This publication has 8 references indexed in Scilit:
- k -Metric antidimension: A privacy measure for social graphsInformation Sciences, 2016
- A Two-Stage Deanonymization Attack against Anonymized Social NetworksIEEE Transactions on Computers, 2012
- De-anonymizing Social Networks2009
- Towards identity anonymization on graphs2008
- Preserving Privacy in Social Networks Against Neighborhood Attacks2008
- Wherefore art thou r3579x?2007
- On the Metric Dimension of Cartesian Products of GraphsSIAM Journal on Discrete Mathematics, 2007
- Resolvability in graphs and the metric dimension of a graphDiscrete Applied Mathematics, 2000