Determining sets, resolving sets, and the exchange property
From MaRDI portal
Publication:968219
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.
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
Cites work
- scientific article; zbMATH DE number 3906528 (Why is no real title available?)
- scientific article; zbMATH DE number 4053685 (Why is no real title available?)
- scientific article; zbMATH DE number 3494441 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- scientific article; zbMATH DE number 894528 (Why is no real title available?)
- Automorphisms and distinguishing numbers of geometric cliques
- Destroying automorphisms by fixing nodes
- Identifying graph automorphisms using determining sets
- Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
- On \(k\)-dimensional graphs and their bases
- On the Complexity of Canonical Labeling of Strongly Regular Graphs
- On the Metric Dimension of Cartesian Products of Graphs
- Resolvability in graphs and the metric dimension of a graph
- The determining number of a Cartesian product
- Using determining sets to distinguish Kneser graphs
Cited in
(16)- Minimum partition of an \(r\)-independence system
- Is it possible to determine a point lying in a simplex if we know the distances from the vertices?
- On metric orbit spaces and metric dimension
- The metric dimension of metric manifolds
- On maximal det-independent (res-independent) sets in graphs
- Exchange property for resolving sets in power graphs
- On redundant locating-dominating sets
- Power graphs and exchange property for resolving sets
- Elimination properties for minimal dominating sets of graphs
- The metric dimension of geometric spaces
- On the metric dimension of certain metric manifolds
- On the metric dimension and diameter of circulant graphs with three jumps
- On the metric basis in wheels with consecutive missing spokes
- The full automorphism groups, determining sets and resolving sets of coprime graphs
- The metric dimension of metric spaces
- On resolvability of a graph associated to a finite vector space
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)
