Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516049 | Journal of Combinatorial Theory, Series B | 2005 | 11 Pages |
Abstract
It is proved that by deleting at most 5 edges every planar (simple) graph of order at least 2 can be reduced to a graph having a non-trivial automorphism. Moreover, the bound of 5 edges cannot be lowered to 4.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
V.A. Aksionov, O.V. Borodin, L.S. Mel'nikov, G. Sabidussi, M. Stiebitz, B. Toft,