On the minimum weight of a 3-connected 1-planar graph
Bull. Korean Math. Soc. 2017 Vol. 54, No. 3, 763-787
https://doi.org/10.4134/BKMS.b160296
Published online May 31, 2017
Zai Ping Lu and Ning Song
Nankai University, Nankai University
Abstract : A graph is called \emph{$1$-planar} if it can be drawn in the Euclidean plane $\mathbb{R}^2$ such that each edge is crossed by at most one other edge. The \emph{weight} of an edge is the sum of degrees of two ends. It is known that every planar graph of minimum degree $\delta\ge3$ has an edge with weight at most $13$. In the present paper, we show the existence of edges with weight at most $25$ in $3$-connected $1$-planar graphs.
Keywords : 1-planar graph, weight, light edge
MSC numbers : 05C10, 68R10
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd