Properties ofπ-skew Graphs with Applications  

作　　者：Zhang Dong OUYANG Feng Ming DONG Rui Xue ZHANG Eng Guan TAY 

机构地区：[1]School of Mathematics and Computational Sciences,Hu’nan First Normal University,Changsha 410205,P.R.China [2]Mathematics and Mathematics Education,National Institute of Education,Nanyang Technological University,637616,Singapore

出　　处：《Acta Mathematica Sinica,English Series》2021年第4期641-656,共16页数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China(Grant No.11301169);Hu’nan Provincial Natural Science Foundation of China(Grant No.2017JJ2055);Scientific Research Fund of Hu’nan Provincial Education Department(Grant No.18A432)。

摘　　要：The skewness of a graph G,denoted by sk(G),is the minimum number of edges in G whose removal results in a planar graph.It is an important parameter that measures how close a graph is to planarity,and it is complementary,and computationally equivalent,to the Maximum Planar Subgraph Problem.For any connected graph G on p vertices and q edges with girth g,one can easily verify that sk(G)≥π(G),whereπ(G)=[q−g/g−2(p−2)],and the graph G is said to beπ-skew if equality holds.The concept ofπ-skew was first proposed by G.L.Chia and C.L.Lee.Theπ-skew graphs with girth 3 are precisely the graphs that contain a triangulation as a spanning subgraph.The purpose of this paper is to explore the properties ofπ-skew graphs.Some families ofπ-skew graphs are obtained by applying these properties,including join of two graphs,complete multipartite graphs and Cartesian product of two graphs.We also discuss the threshold for the existence of a spanning triangulation.Among other results some sufficient conditions regarding the regularity and size of a graph,which ensure a spanning triangulation,are given.

关 键 词：Skewness of graph crossing number of graph Cartesian product join product π-skew 

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