Determining sets, resolving sets, and the exchange property - Mathematics > CombinatoricsReportar como inadecuado

Determining sets, resolving sets, and the exchange property - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Debra Boutin



Documentos relacionados