Light Subgraphs in the Family of 1-Planar Graphs with High Minimum Degree  

作　　者：Xin ZHANG Gui Zhen LIU Jian Liang WU 

机构地区：[1]School of Mathematics,Shandong University

出　　处：《Acta Mathematica Sinica,English Series》2012年第6期1155-1168,共14页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China (Grant Nos. 10971121, 11026184, 61070230);Research Fund for the Doctoral Program of Higher Education (Grant No. 20100131120017);Graduate Independent Innovation Foundation of Shandong University (Grant No. yzc10040);the financial support from the Chinese Ministry of Education Prize for Academic Doctoral Fellows

摘　　要：A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V （K1 ∪ K2） with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1 V （K1∪K2） with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V （K1 ∪ K2） with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1 V （K1∪K2） with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.

关 键 词：1-Planar graph LIGHTNESS HEIGHT DISCHARGING 

分 类 号：O157.5[理学—数学] Q98[理学—基础数学]