Properties of π -skew Graphs with Applications

来源 :数学学报(英文版) | 被引量 : 0次 | 上传用户:qweasd123qweqwe
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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 suffi cient conditions regarding the regularity and size of a graph,which ensure a spanning triangulation,are given.
其他文献