The Structure of (<i>k</i>,<i>l</i>)-recursive Maximal Planar Graph

Xiang’en CHEN; Ting LI

doi:10.11999/JEIT171021

Volume 40 Issue 9

Aug. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2018 > 40(9): 2281-2286

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

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

PDF( 2063 KB)

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

doi: 10.11999/JEIT171021

Xiang’en CHEN^,,
Ting LI

College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Funds: The National Natural Science Foundation of China (11761064, 61163037, 61163054)

Received Date: 2017-11-01
Rev Recd Date: 2018-06-04

Available Online: 2018-07-12

Publish Date: 2018-09-01

Abstract

Abstract

For a maximal planar graph G, the operation of extending 3-wheel is a process from G to G∨v, where v is a new vertex embedded in some triangular face xyz of G and G∨v 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 K₄ 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.
- Planar graph,
- Maximal planar graph,
- Extending 3-wheel,
- Recursive maximal planar graph

FullText(HTML)

References(17)

References

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

Relative Articles

Supplements(0)

Cited By

Proportional views