Article ID Journal Published Year Pages File Type
418875 Discrete Applied Mathematics 2014 6 Pages PDF
Abstract

A 1-planar graph is a graph that can be drawn in the plane such that each edge is crossed by at most one other edge. For a fixed integer k≥2k≥2 and a simple 1-planar graph GG on nn vertices it is proven that 2(n−1)k+O(n)2(n−1)k+O(n) is an upper bound on the sum of the kk-th powers of the degrees of GG.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,