摘要
对于一个平面图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.
作者
陈祥恩
李婷
CHEN Xiang＇en;LI Ting(College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)
出处
《电子与信息学报》
EI
CSCD
北大核心
2018年第9期2281-2286,共6页
Journal of Electronics & Information Technology
基金
国家自然科学基金(11761064
61163037
61163054)~~
关键词
平面图
极大平面图
扩3-轮
递归极大平面图
Planar graph
Maximal planar graph
Extending 3-wheel
Recursive maximal planar graph
