探索对奇边优美差全着色封闭的图格

张明军; 杨见青; 姚兵

工程数学学报 ›› 2024, Vol. 41 ›› Issue (2) : 311 -325.

探索对奇边优美差全着色封闭的图格

张明军, 杨见青, 姚兵

作者信息 +

Author information +

文章历史 +

摘要

为深入拓扑编码的研究，定义了新的图全标号和图全着色：（集有序）奇边优美差全标号/全着色，孪生（集有序）奇边优美差全标号/全着色。证明了若偶图T承认集有序奇优美标号，则给偶图T添加m片叶子后得到的偶图T^*承认一个奇边优美差全着色；每棵树承认一个奇边优美差全着色。定理的证明均可转化为可行、有效的算法。为建立随机着色的图格，给出随机添加叶子的奇边优美差全着色算法和一致-k^*优美差算法，建立了对奇边优美差全着色封闭的一致-k^*优美差图格、孪生一致-（k^*,n^*）优美差图格，以及一个图格同态到另一个图格的图格同态。