(k,l)-递归极大平面图的结构  

The Structure of (k,l)-recursive Maximal Planar Graph

作　　者：陈祥恩 李婷 CHEN Xiang＇en;LI Ting(College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

机构地区：[1]西北师范大学数学与统计学院,兰州730070

出　　处：《电子与信息学报》2018年第9期2281-2286,共6页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(11761064;61163037;61163054)~~

摘　　要：对于一个平面图G实施扩3-轮运算是指在G的某个三角形面xyz内添加一个新顶点v,使v与x, y, z均相邻,最后得到一个阶为|V(G)|+1的平面图的过程。一个递归极大平面图是指从平面图K_4出发,逐次实施扩3-轮运算而得到的极大平面图。所谓一个(k,l)-递归极大平面图是指一个递归极大平面图,它恰好有k个度为3的顶点,并且任意两个3度顶点之间的距离均为l。该文对(k,l)-递归极大平面图的存在性问题做了探讨,刻画了(3,2)-及(2,3)-递归极大平面图的结构。For a maximal planar graph G, the operation of extending 3-wheel is a process from G to GVv, where v is a new vertex embedded in some triangular face xyz of G and GVv is a graph of order ｜V（G）｜＋1 obtained from G by connecting v to each one of x, y, z with one edge. A recursive maximal planar graph is a maximal planar graph obtained from K4 by extending 3-wheel continuously. A （k,l）-recursive maximal planar graph is a recursive maximal planar graph with exactly k vertices of degree 3 so that the distance between arbitrary two vertices of degree k is l. The existence of （k,l）-recursive maximal planar graph is discussed and the structures of （3,2）-as well as （2,3）-recursive maximal planar graphs are described.

关 键 词：平面图 极大平面图 扩3-轮 递归极大平面图 

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