一种特殊的多米诺扩缩运算

发布时间：2018-10-11 10:18

【摘要】：该文提出一种称为334扩缩运算的多米诺扩缩运算。使用该运算构造了一类特殊的极大平面图——334-型极大平面图,证明了该类图均为树型2-色不变圈着色,且每个4k-阶334-型极大平面图恰有2~(k-1)个2-色不变圈着色及2~(k-2)个树着色。证明了该运算可用于构造纯树着色极大平面图,并提出猜想:若极大平面图G是纯树(纯圈,混合)着色,则对G实施334扩(缩)轮运算后,所得之图仍是纯树(纯圈,混合)着色。
[Abstract]:In this paper, a domino-scaling operation called 334 scaling operation is proposed. By using this operation, a special maximal planar graph of type 334-type is constructed. It is proved that all of these graphs are tree-type 2-chromatic invariant cycle coloring, and each maximal planar graph of order 334- has exactly 2 ~ (k-1) 2-chromatic invariant cycle coloring and 2 ~ (k-2) tree coloring. It is proved that this operation can be used to construct the coloring maximal planar graph of pure trees. If G is a pure tree (pure cycle, mixed) coloring, the graph obtained is still pure tree (pure cycle) after 334 extension (contraction) round operation of G. Mixed) coloring
【作者单位】： 北京大学信息科学技术学院;北京大学高可信软件技术教育部重点实验室;
【基金】：国家973计划项目(2013CB329600) 国家自然科学基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)~~
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 叶载良;极大平面图的构造[J];纺织高校基础科学学报;2003年03期

2 韩忠海,杨爱民;关于(4,6)-正则极大平面图的构造[J];华北工学院学报;2004年06期

3 叶载良;;极大平面图的面嵌入图[J];纺织高校基础科学学报;2005年04期

4 韩忠海;;12阶的(4,8)-正则极大平面图的不存在性[J];山西农业大学学报(自然科学版);2008年01期

5 谢力同;极大平面图的组合运算[J];系统科学与数学;1993年04期

6 王绍文;;极大平面图的构成算法[J];北京机械工业学院学报;1997年02期

7 王绍文;极大平面图结构研究[J];光子学报;1998年02期

8 王绍文;;同构极大平面图研究[J];北京机械工业学院学报;1998年01期

9 王绍文;构造极大平面图的三种方法[J];北京机械工业学院学报;1999年01期

10 许寿椿,刘恒军,杨丽丽,朱英,许怀皓;着五色极大平面图的对偶2～3色子图及五色点消减的实验研究[J];中央民族大学学报(自然科学版);1999年01期

相关硕士学位论文 前6条

1 李永丽;（k，l，m）-正则极大平面图[D];山西大学;2010年

2 韩忠海;（K，L）-正则极大平面图[D];山西大学;2005年

3 杨宁;极大平面图略型着色的计算机辅助研究[D];中央民族大学;2005年

4 程斌;极大平面图最简非树型着色的统计分析与生成[D];中央民族大学;2005年

5 宝力高;极大平面图最简非树型着色的统计分析与生成[D];中央民族大学;2005年

6 刘茜;极大平面图的构造方法与几类特殊图的色数分析[D];南京信息工程大学;2008年

，

本文编号：2263824