学位论文 > 优秀研究生学位论文题录展示

若干图的素标号和FFI集问题研究

作　者: 赵平仲
导　师: 林晓惠
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 标号 素标号 FFI集
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 7次
引　用: 0次
阅　读: 论文下载
 

内容摘要


标号问题是图论领域很重要的研究课题之一，本文利用算法与分析中的回溯与分支限界的理论设计程序求解了几类图的标号问题，将计算机构造证明与数学证明相结合研究了两类标号问题：素标号、FFI集。素标号是由Entringer提出，由Tout，Dabboucy和Howalla给出了树是素图的猜想。目前，经过证明是素图的树有：路径，星图，毛毛虫，完全二叉树，蜘蛛图，橄榄树，所有顶点数小于50的树。其它的具有素标号的图包括：所有的圈，C2k和Cn的分解体，当n是偶数时Wn，完全图Kn（n≥4），Fans，Helms，Flowers，Stars，K2,n与K3,n（n≠3,7），Books，Snm，Cn（?）Pm，Pn×（?）2（当且仅当n=2或n是奇数）。Vilfred等给出了猜想：当n为素数并且n>m时Pm×Pn为素图，Sundaram等证明了这个猜想而且还证明了当n为素数时，Pn×Pn是素图。Carlson证明了广义的Books和Cn-Snakes图是素图。Yao，Cheng，Zhongfu等人给出了这样的结论：如果一个图的最大的度数至少是n／2（n为顶点数）时，这个图为素图。FFI集是由Harris Kwong，S．M．Lee，Ho Kuen Ng在2006年首次提出的概念，即：{if（G）|f是图G的Friendly标号}并给出了FFI（Cn），S．M．Lee等证明了下列图的FI（G）：树，圈，棱柱，M（?）bius梯等。随后Wai Chee Shiu，Harris Kwong证明了P2×Pn具有FFI（G）．鉴于以上问题的研究意义以及广义Petersen图P（n，k）和Kn（?）del图W（3，n）的重要性，本文证明了广义的Petersen图P（n，1）当n≤2500且n是偶数时是素图，以及Kn（?）del图W（3,n）当n≤130且n是偶数时也是素图。本文还给出了广义Petersen图P（n,2）的FFI集：

全文目录


相似论文

  1. 基于GIS_GPS的武警作战指挥系统关键技术研究与实现,E211
  2. 城市突发公共事件伤员救治出救点选择与车辆路径集成优化研究,X928.04;U116.2
  3. 循环圈算术标号的研究,O157.5
  4. 关于路、圈并图优美性的研究,O157.5
  5. 关于DNA图及其标号图的研究,O157.5
  6. A（m，n）图的顶点优美标号及超顶点优美标号的研究,O157.5
  7. 两类毛毛虫的多级距离数,O157.5
  8. 图的{P_r}-自由着色,O157.5
  9. 完全二部图K_（n，n）的循环圈分解及边—平衡指数集,O157.5
  10. 树状图的路覆盖问题及其应用,O157.5
  11. 基于场景和属性的需求引出及形式化建模,TP311.52
  12. K_（4-e）链的边—平衡指数集,O157.5
  13. 图的（p，1）-全标号及图的弱邻点可区分的染色问题,O157.5
  14. 低标号砂浆空斗墙砌体的抗震性能及其加固关键问题研究,TU746.3
  15. 基于不动点理论的遗传算法研究,TP18
  16. 邻点可区分的染色和两种特殊的全染色问题,O157.5
  17. 带有邻域限制的三类染色问题,O157.5
  18. 基于CHAM的类测试用例生成,TP311.52
  19. 图C_n×P_m的边—平衡指数集研究,O157.5
  20. 广义Petersen图的条件着色和L（2，1）-标号,O157.5
  21. 图的（d，1）-全标号及游戏着色,O157.5

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com