Automorphisms and distinguishing numbers of geometric cliques

被引:6
作者
Albertson, Michael O. [1 ]
Boutin, Debra L. [2 ]
机构
[1] Smith Coll, Dept Math & Stat, Northampton, MA 01063 USA
[2] Hamilton Coll, Dept Math, Clinton, NY 13323 USA
关键词
geometric automorphism; geometric clique; distinguishing number; determining set; convex hull boundary;
D O I
10.1007/s00454-008-9066-x
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A geometric automorphism is an automorphism of a geometric graph that preserves crossings and noncrossings of edges. We prove two theorems constraining the action of a geometric automorphism on the boundary of the convex hull of a geometric clique. First, any geometric automorphism that fixes the boundary of the convex hull fixes the entire clique. Second, if the boundary of the convex hull contains at least four vertices, then it is invariant under every geometric automorphism. We use these results, and the theory of determining sets, to prove that every geometric n-clique in which n >= 7 and the boundary of the convex hull contains at least four vertices is 2-distinguishable.
引用
收藏
页码:778 / 785
页数:8
相关论文
共 15 条
[1]  
Albertson M.O., 1996, ELECT J COMB, V3
[2]   Distinguishing geometric graphs [J].
Albertson, Michael O. ;
Boutin, Debra L. .
JOURNAL OF GRAPH THEORY, 2006, 53 (02) :135-150
[3]  
ALBERTSON MO, 2007, ELECT J COMB, V14
[4]  
ALBERTSON MO, 2005, ELECT J COMB, V12
[5]  
[Anonymous], HDB DISCRETE COMPUTA
[6]   The distinguishing number of the hypercube [J].
Bogstad, B ;
Cowen, LJ .
DISCRETE MATHEMATICS, 2004, 283 (1-3) :29-35
[7]  
BOUTIN DL, 2006, ELECT J COMB, V13
[8]  
CHAN M, 2006, ELECT J COMB, V13
[9]   The distinguishing number of the direct product and wreath product action [J].
Chan, Melody .
JOURNAL OF ALGEBRAIC COMBINATORICS, 2006, 24 (03) :331-345
[10]  
COLLINS KL, 2006, ELECT J COMB, V13