Upper bound on the sum of powers of the degrees of graphs with few crossings per edge

摘要

A graph is q-planar if it can be drawn in the plane so that each edge is crossed by at most q other edges. For fixed integers q = 1 and k = 2, it is proven that 2(n -1)(k) + o(n) is an asymptotically tight upper bound on the sum of the k-th powers of the degrees of any simple q-planar graph with order n. As a result, an open problem listed at the end of the paper J. Czap, J. Harant, D. Huak, Discrete Appi. Math. 165 (2014) 146-151 is solved. (C) 2019 Elsevier Inc. All rights reserved.