|
Organizers |
Deeply asymmetric planar graphs
by
G. Sabidussi
Université de Montréal
Coauthors: V. Aksionov, O. Borodin, L. Melnikov, M. Stiebitz, B.Toft
Every planar graph has a vertex of degree at most 5. From this it follows easily that every planar graph contains a set of at most 10 edges whose removal produces a graph having an involutory automorphism. Can the number 10 be lowered? The answer is, 5 edges suffice. Moreover, 5 is best possible: there exist planar graphs which are deeply asymmetric in the sense that the removal of any set of at most 4 edges leaves a graph that has no non-trivial automorphism.
Date received: April 28, 2001
Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cags-76.