A structural property of planar graphs

MaRDI QIDQ2713988zbMATH OpenFDO

Authors Valerii A. Aksenov, Oleg V. Borodin, A. N. Glebov

Publication date 10 June 2001

Published in Diskretnyĭ Analiz i Issledovanie Operatsiĭ. Seriya 1 (Search for Journal in Brave)

zbMATH Keywords

minimum weight edgeplane maptheorem of Kotzig

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

An edge in a plane map is called weak if it is incident with two triangle faces, and semi-weak if it is incident with only one triangle face. The weight of an edge is the sum of the degrees of its vertices. In the article under review, it is proven that every connected plane map with at least two vertices contains either two vertices with the sum of degrees at most 4, or two vertices of degree 3 with distance 2 between them, or a weak edge of weight at most 11, or a semi-weak edge of weight at most 9, or, in addition, an edge of weight at most 7. All the bounds are the best possible as is shown by explicit constructions.NEWLINENEWLINENEWLINEThis result is an enhancement of a similar structural theorem by \textit{V. A. Aksenov, O. V. Borodin, L. S. Mel'nikov, G. Sabidussi, M. Stiebitz}, and \textit{B. Toft} [J. Comb. Theory, Ser. B (to appear)], which was used there to show that from every plane map it is possible to obtain a map with a nontrivial automorphism by removing at most 5 edges.

Recommendations

• A planarity criterion for graphs
• A structural theorem for planar graphs with some applications
• An algebraic characterization of planar graphs
• scientific article; zbMATH DE number 1019602
• Another characterisation of planar graphs
• scientific article; zbMATH DE number 475620
• Structural properties for certain classes of infinite planar graphs
• scientific article; zbMATH DE number 125449
• A criterion for the planarity of a graph

Cited in

(4)

• Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
• Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs
• scientific article; zbMATH DE number 889952 (Why is no real title available?)
• Exact asymptotics of small deviations for a stationary Ornstein-Uhlenbeck process and some Gaussian diffusion processes in the L p -norm, 2 ≤ p ≤ ∞

This page was built for publication: A structural property of planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2713988)