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. Hudák, Discrete Appl. Math. 165 (2014) 146–151 is solved.