高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

陈祥恩 李婷

陈祥恩, 李婷. (k,l)-递归极大平面图的结构[J]. 电子与信息学报, 2018, 40(9): 2281-2286. doi: 10.11999/JEIT171021
引用本文: 陈祥恩, 李婷. (k,l)-递归极大平面图的结构[J]. 电子与信息学报, 2018, 40(9): 2281-2286. doi: 10.11999/JEIT171021
Xiang’en CHEN, Ting LI. The Structure of (k,l)-recursive Maximal Planar Graph[J]. Journal of Electronics & Information Technology, 2018, 40(9): 2281-2286. doi: 10.11999/JEIT171021
Citation: Xiang’en CHEN, Ting LI. The Structure of (k,l)-recursive Maximal Planar Graph[J]. Journal of Electronics & Information Technology, 2018, 40(9): 2281-2286. doi: 10.11999/JEIT171021

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

doi: 10.11999/JEIT171021
基金项目: 国家自然科学基金(11761064, 61163037, 61163054)
详细信息
    作者简介:

    陈祥恩:男,1965年生,教授,主要研究方向为图论及其应用

    李婷:女,1993年生,硕士生,研究方向为图论及其应用

    通讯作者:

    陈祥恩  chenxe@nwnu.edu.cn

  • 中图分类号: O157.5

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

Funds: The National Natural Science Foundation of China (11761064, 61163037, 61163054)
  • 摘要: 对于一个平面图G实施扩3-轮运算是指在G的某个三角形面xyz内添加一个新顶点v,使vx, y, z均相邻,最后得到一个阶为|V(G)|+1的平面图的过程。一个递归极大平面图是指从平面图K4出发,逐次实施扩3-轮运算而得到的极大平面图。 所谓一个(k,l)-递归极大平面图是指一个递归极大平面图,它恰好有k个度为3的顶点,并且任意两个3度顶点之间的距离均为l。该文对(k,l)-递归极大平面图的存在性问题做了探讨,刻画了(3,2)-及(2,3)-递归极大平面图的结构。
  • 图  1  阶分别为4,7,10的递归极大平面图

    图  2  命题3所述图的结构

    图  3  命题3证明过程中出现的递归极大平面图

    图  4  定理4证明过程中出现的递归极大平面图

    图  5  A型的(2,3)-递归极大平面图

    图  6  6阶的B型(2,3)-递归极大平面图

    图  7  定理7证明里(1)中的B型(2,3)-递归极大平面图

    图  8  定理7证明里(2)中出现的(2,3)-递归极大平面图

    图  9  定理7证明里(2)中出现的另一个(2,3)-递归极大平面图

    图  10  C型的(2,3)-递归极大平面图

    图  11  A型递归极大平面图

    图  12  B型的(3,2)-递归极大平面图

    图  13  C型的(3,2)-递归极大平面图

    图  14  D型的(3,2)-递归极大平面图

  • APPEL K and HAKEN W. The solution of the four-color map problem[J]. Science American, 1977, 237(4): 108–121 doi: 10.1038/scientificamerican1077-108
    APPEL K and HAKEN W. Every planar map is four colorable, I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21(3): 429–490.
    APPEL K, HAKEN W, and KOCH J. Every planar map is four-colorable, II: Reducibility[J]. Illinois Journal of Mathematics, 1977, 21(3): 491–567.
    王邵文. 构造极大平面图的圈加点法[J]. 北京机械工业学院学报, 2000, 15(1): 26–29

    WANG Shaowen. Method of cycle add-point to construct a maximum plate graph[J]. Journal of Beijing Institute of Machinery, 2000, 15(1): 26–29
    王邵文. 构造极大平面图的三种方法[J]. 北京机械工业学院学报, 1999, 14(1): 16–22

    WANG Shaowen. Three methods to construct maximum plain graph[J]. Journal of Beijing Institute of Machinery, 1999, 14(1): 16–22
    BRINKMANN G and MCKAY B D. Construction of planar triangulations with minimum degree 5[J]. Discrete Mathematics, 2005, 301(2-3): 147–163 doi: 10.1016/j.disc.2005.06.019
    GAO Z C, URRUTIA J, and WANG J Y. Diagonal flips in labeled planar triangulations[J]. Graphs and Combinatorics, 2004, 17(4): 647–656 doi: 10.1007/s003730170006
    BOSE P, JANSENS D, VAN RENSSEN A, et al. Making triangulations 4-connected using flips[C]. Proceedings of the 23rd Canadian Conference on Computational Geometry, Toronto, 2014: 187–197.
    LI Zepeng, ZHU Enqiang, SHAO Zehui, et al. Size of edge-critical uniquely 3-colorable planar graphs[J]. Discrete Mathematics, 2016, 339(4): 1242–1250 doi: 10.1016/j.disc.2015.11.009
    LI Zepeng, ZHU Enqiang, SHAO Zehui, et al. A note on uniquely 3-colorable planar graphs[J]. International Journal of Computer Mathematics, 2017, 94(5): 1028–1035 doi: 10.1080/00207160.2016.1167196
    许进. 极大平面图的结构与着色理论: (1)色多项式递推公式与四色猜想[J]. 电子与信息学报, 2016, 38(4): 763–779 doi: 10.11999/JEIT160072

    XU Jin. Theory on the structure and coloring of maximal planar graphs: (1) Recursion formula of chromatic polynomial and four-color conjecture[J]. Journal of Electronics&Information Technology, 2016, 38(4): 763–779 doi: 10.11999/JEIT160072
    许进. 极大平面图的结构与着色理论: (2)多米诺构形与扩缩运算[J]. 电子与信息学报, 2016, 38(6): 1271–1327 doi: 10.11999/JEIT160224

    XU Jin. Theory on the structure and coloring of maximal planar graphs: (2)Domino configurations and extending-contracting operations[J]. Journal of Electronics&Information Technology, 2016, 38(6): 1271–1327 doi: 10.11999/JEIT160224
    许进. 极大平面图的结构与着色理论: (3) 纯树着色与唯一4色极大平面图猜想[J]. 电子与信息学报, 2016, 38(6): 1328–1363 doi: 10.11999/JEIT160409

    XU Jin. Theory on the structure and coloring of maximal planar graphs: (3) Purely tree-colorable and uniquely 4-colorable maximal planar graph conjecture[J]. Journal of Electronics&Information Technology, 2016, 38(6): 1328–1363 doi: 10.11999/JEIT160409
    许进. 极大平面图的结构与着色理论: (4)σ-运算与Kempe等价类[J]. 电子与信息学报, 2016, 38(7): 1557–1585 doi: 10.11999/JEIT160483

    XU Jin. Theory on the structure and coloring of maximal planar graphs: (4) σ-operations and Kempe equivalent classes[J]. Journal of Electronics&Information Technology, 2016, 38(7): 1557–1585 doi: 10.11999/JEIT160483
    XU Jin, LI Zepeng, and ZHU Enqiang. On purely tree-colorable planar graphs[J]. Information Processing Letter, 2016, 116(8): 532–536 doi: 10.1016/j.ipl.2016.03.011
    许进, 李泽鹏, 朱恩强. 极大平面图理论研究进展[J]. 计算机学报, 2015, 38(8): 1680–1704 doi: 10.11897/SP.J.1016.2015.01680

    XU Jin, LI Zepeng, and ZHU Enqiang. Research progress on maximal planar graphs[J]. Chinese Journal of Computers, 2015, 38(8): 1680–1704 doi: 10.11897/SP.J.1016.2015.01680
    ZHU Enqiang, LI Zepeng, SHAO Zehui, et al. Acyclically 4-colorable triangulations[J]. Information Processing Letter, 2016, 116(6): 401–408 doi: 10.1016/j.ipl.2015.12.005
  • 加载中
图(14)
计量
  • 文章访问数:  1613
  • HTML全文浏览量:  607
  • PDF下载量:  24
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-11-01
  • 修回日期:  2018-06-04
  • 网络出版日期:  2018-07-12
  • 刊出日期:  2018-09-01

目录

    /

    返回文章
    返回