图的完全可定向性

论文摘要

设D是简单图G的一个无圈定向.若改变D中的一条弧的方向会产生有向圈,则称这条弧为D的相依边.用d（D）来表示D中相依边的条数,dmin（G）和dmax（G）分别表示G的所有无圈定向中相依边数的最小值和最大值.若对满足dmin（G）≤k≤dmax（G）的所有k,都存在G的无圈定向D使得d（D）=k,则称G是完全可定向的.图的完全可定向问题首先由Fisher, Fraughnaugh, Langley和West开始研究的.最近,台湾一些学者给出若干有趣的研究结果[8-10,12,13].本学位论文研究一些特殊图的完全可定向问题,如圈的平方、圈的立方、2-外平面图、无爪3-退化图等.本文共分5章.在第1章中,我们给出所用到的基本概念,简述了相关领域的研究现状并呈现了本文的主要研究结果.在第2章,我们证明了无爪3-退化图和不含K3（2）作为导出子图的2-外平面图是完全可定向的.在第3章,我们证明了：若dmax（G）≤6,则G是完全可定向的.在第4章,我们确定了dmin（Cn2）的值并证明了当n≥7时Cn2是完全可定向的.在第5章,我们确定了dmin（Cn3）的值并证明了当n≥9时Cn3是完全可定向的.

论文目录

• 摘要
• ABSTRACT
• 目录
• 1 绪论
• 1.1 基本概念
• 1.2 完全可定向的研究概况
• 1.3 本文主要结果
• 2 无爪3-退化图和2-外平面图的完全可定向性
• 2.1 两个引理
• 2.2 完全可定向性
• max的极值'>3 关于d_max的极值
• n²的完全可定向性'>4 C_n²的完全可定向性
• n²的最小相依边数'>4.1 C_n²的最小相依边数
• n²的完全可定向性'>4.2 C_n²的完全可定向性
• n³的完全可定向性'>5 C_n³的完全可定向性
• n³的最小相依边数'>5.1 C_n³的最小相依边数
• n³的完全可定向性'>5.2 C_n³的完全可定向性
• 参考文献
• 攻读学位期间取得的研究成果
• 致谢