An upper bound on the sum of powers of the degrees of simple 1-planar graphs

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≥2 and a simple 1-planar graph G on n vertices it is proven that 2(n−1)k+O(n) is an upper bound on the sum of the k-th powers of the degrees of G.

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2014-03, Vol.165, p.146-151
Main Authors: Czap, Július, Harant, Jochen, Hudák, Dávid
Format: Article
Language:English
Subjects:
1-planar graph
Degree sum
Graphs
Integers
Mathematical analysis
Planes
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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≥2 and a simple 1-planar graph G on n vertices it is proven that 2(n−1)k+O(n) is an upper bound on the sum of the k-th powers of the degrees of G.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2012.11.001