Determining sets, resolving sets, and the exchange property - Mathematics > CombinatoricsReport as inadecuate




Determining sets, resolving sets, and the exchange property - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

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



Author: Debra Boutin

Source: https://arxiv.org/







Related documents