zbMATH — the first resource for mathematics

Deeply asymmetric planar graphs. (English) Zbl 1070.05031
Summary: 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.

05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX Cite
Full Text: DOI
[1] Borodin, O.V., Joint extension of two theorems of kotzig on 3-polytopes, Combinatorica, 13, 121-125, (1993) · Zbl 0777.05050
[2] Erdös, P.; Rényi, A., Asymmetric graphs, Acta math. acad. sci. hungar., 14, 295-315, (1963) · Zbl 0118.18901
[3] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat.-fyz. casopis., 5, 101-113, (1955)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.