Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651145 | Discrete Mathematics | 2007 | 12 Pages |
Abstract
A graph is called 1-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge. In the paper, we study the existence of subgraphs of bounded degrees in 1-planar graphs. It is shown that each 1-planar graph contains a vertex of degree at most 7; we also prove that each 3-connected 1-planar graph contains an edge with both endvertices of degrees at most 20, and we present similar results concerning bigger structures in 1-planar graphs with additional constraints.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Igor Fabrici, Tomáš Madaras,