Determining sets, resolving sets, and the exchange property

Details Determining sets, resolving sets, and the exchange property Determining sets, resolving sets, and the exchange property

2008-08-10

arxiv.org/abs/0808.1427v1

Mathematics

Combinatorics

Scientific paper

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 r\in R, then there exists s\in 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 n\geq 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.

Affiliated with

Also associated with

No associations

Rating

Determining sets, resolving sets, and the exchange property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Determining sets, resolving sets, and the exchange property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining sets, resolving sets, and the exchange property will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-492563