| 摘 要： | 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.
|
