Determining sets, resolving sets, and the exchange property

DOI10.1007/S00373-010-0880-6zbMATH Open1205.05103arXiv0808.1427OpenAlexW2034385267MaRDI QIDQ968219FDOQ968219

Authors: Debra L. Boutin 

Publication date: 5 May 2010

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: A subset U of vertices of a graph G is called a determining set if every automorphism of G is uniquely determined by its action on the vertices of U. A subset W is called a resolving set if every vertex in G is uniquely determined by its distances to the vertices of W. Determining (resolving) sets are said to have the exchange property in G if whenever S and R are minimal determining (resolving) sets for G and rin R, then there exists sin S so that S-{s}cup {r} is a minimal determining (resolving) set. This work examines graph families in which these sets do, or do not, have the exchange property. This paper shows that neither determining sets nor resolving sets have the exchange property in all graphs, but that both have the exchange property in trees. It also gives an infinite graph family (n-wheels where ngeq 8) in which determining sets have the exchange property but resolving sets do not. Further, this paper provides necessary and sufficient conditions for determining sets to have the exchange property in an outerplanar graph.

Full work available at URL: https://arxiv.org/abs/0808.1427

Recommendations

• Exchange properties of finite set-systems
• scientific article; zbMATH DE number 1556746
• Power graphs and exchange property for resolving sets
• Set-Menger and related properties
• The properties of exchange and ends of optional sets
• Exchange property for resolving sets in power graphs
• Establishing a property of finite sets
• On set-theoretic intersections
• Determination of set-membership identifiability sets

zbMATH Keywords

exchange propertyresolving setsdetermining sets

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On \(k\)-dimensional graphs and their bases
• Destroying automorphisms by fixing nodes
• Title not available (Why is that?)
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Identifying graph automorphisms using determining sets
• Title not available (Why is that?)
• Using determining sets to distinguish Kneser graphs
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Automorphisms and distinguishing numbers of geometric cliques
• The determining number of a Cartesian product

Cited In (16)

• On the metric dimension of certain metric manifolds
• On the metric dimension and diameter of circulant graphs with three jumps
• Elimination properties for minimal dominating sets of graphs
• Is it possible to determine a point lying in a simplex if we know the distances from the vertices?
• The full automorphism groups, determining sets and resolving sets of coprime graphs
• The metric dimension of metric spaces
• On maximal det-independent (res-independent) sets in graphs
• The metric dimension of geometric spaces
• On the metric basis in wheels with consecutive missing spokes
• Power graphs and exchange property for resolving sets
• Exchange property for resolving sets in power graphs
• On resolvability of a graph associated to a finite vector space
• Minimum partition of an \(r\)-independence system
• On metric orbit spaces and metric dimension
• On redundant locating-dominating sets
• The metric dimension of metric manifolds

This page was built for publication: Determining sets, resolving sets, and the exchange property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968219)