几乎自补图直径和色数.doc

南开大学 硕士学位论文 几乎自补图的直径和色数 姓名：安萍 申请学位级别：硕士 专业：应用数学 指导教师：金应烈 摘要 摘要 一个图Ｇ叫做自补图，如果它与它的补图同构；类似的，一个偶数阶图Ｇ叫 做几乎自补图，如果Ｇ同构与它的一个几乎补图口一Ｍ：Ｇ型Ｇｃ一．Ａ４，其中 Ｍ为补图６产中的一个完美匹配。本文重点研究了自补图和几乎自补图的性质和 区别。第三章主要讨论了白补图的直径和色数，并在此基础上，在第四章详细地 研究了几乎自补图的性质、直径、色数。证明了连通的几乎自补图的直径只能是 ２，３，４。并对每一个正整数ｎ≥３，构造了２ｎ阶直径分别为３、４的几乎自补图；对 每一个正整数仙≥４，构造了２竹阶直径为２的几乎自补图。同时，证明了２ｎ阶 几乎自补图色数ｘ（Ｇ）满足『ｖ伍１≤ｘ（Ｇ。）≤ｎ，通过构造我们证明了不等式的 上界是最好的，且当￣／元为正整数时，下界也是最好的。 关键词：白补图，几乎自补图，直径，色数 ＭＲ ０．ｃ．（２０００）：０５Ｃ１２，０５Ｃ１５，０５Ｃ６０ Ａｂｓｔｒａｃｔ Ａｂｓｔｒａｃｔ Ａ ｇｒａｐｈ Ｇ ｉｓ ｃａｌｌｅｄ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｚｙ ｇｒａｐｈ，ｉｆ ｉｔ ｉｓ ｉｓｏｍｏｒｐｈｉｃ ｔｏ ｉｔｓ ｃｏｍ－ ｐｌｅｍｅｎｔｓ．Ｓｉｍｉｌａｒｌｙ，Ａ ｇｒａｐｈ Ｇ ｗｉｔｈ ｅＶｅｌｌ ｎｕｍｂｅｒ ｏｆ ｖｅｒｔｉｃｅｓ ｉｓ ｃａｌｌｅｄ ａｌｍｏｓｔ ｓｅｌｆ－ ｃｏｍｐｌｅｍｅｎｔａｒｙ，ｉｆ ｉｔ ｉｓ ｉｓｏｍｏｒｐｈｉｃ ｔ０ ｏｎｅ ｏｆ ｉｔｓ ａｌｍｏｓｔ ｃｏｍｐｌｅｍｅｎｔｓ Ｇ。一Ｍ：Ｇ岂 Ｇ。一Ｍ．ｗｈｅｒｅ Ｍ ｄｅｎｏｔｅｓ ａ ｐｅｒｆ鳅ｍａｔｃｈｉｎｇ ｉｎ ｉｔｓ ｃｏｍｐｌｅｍｅｎｔ Ｇｃ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｐａｙ ａｔｔｅｎｔｉｏｎ ｔｏ ｔｈｅ ｐｒｏｐｅｒｔｉｅｓ ａｎｄ ｄｉｆｆｅｒｅｎｃｅ ｂｅｔｗｆｅｎ ｔｈｅ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ ａｎｄ ｔｈｅ ａｌｍｏｓｔ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ．Ｉｎ ｃｈａｐｔｅｒ ３，ｗｅ ｍａｉｎｌｙ ｃｏｎｓｉｄｅｒ ｔｈｅ ｄｉ— ａｍｅｔｅｒ ａｎｄ ｃｈｒｏｍａｔｉｃ ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ．Ｉｎ ｃｈａｐｔｅｒ ４，ｂａｓｅｄ ｏｎ ｔｈａｔ，ｗｅ ｐｒｅｓｅｎｔ ｓｏｍｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ａｌｍｏｓｔ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ ａｎｄ ｐｒｏｖｅ ｓｏｍｅ ｒｅｓｕｌｔｓ ａｂｏｕｔ ｔｈｅ ｄｉａｍｅｔｅｒ ａｎｄ ｃｈｒｏｍａｔｉｃ ｎｕｍｂｅｒ ｏｆ ａｌｍｏｓｔ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ．ｗｅ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｄｉａｍｅｔｅｒ ｏｆ ｃｏｎｎｅｃｔｅｄ ａｌｍｏｓｔ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ ｍｕｓｔ ｂｅ ２，３ Ｏｒ ４，ａｎｄ ｃｏｏｓｈ＇ｕｃｔ ｃｏｎｎｅｃｔｅｄ ａｌｍｏｓｔ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ ｗｉｔｈ ２ｎ ｖｅｒｔｉｃｅｓ ｈａｖｉｎｇ ｄｉａｍｅｔｅｒ ３，４ ｆｏｒ ｅａｃｈ ｎ≥３ ａｎｄ ｄｉａｍｅｔｅｒ ２ ｆｏｒ ｅａｃｈ ｎ芝４ ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｉｎ ａｄｄｉｔｉｏｎ，ｗｅ ａｌｓｏ ｏｂｔａｉｎ ｔｈａｔ ｆｏｒ ａｎｙ ａｌｍｏｓｔ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈ Ｇｎ ｗｉｔｈ ２ｎ ｖｅｒｔｉｃｅｓ，『、历１≤ｘ（１％）≤ｎ．Ｂｙ ｃｏｎｓｔｒｕｃｔｉｏｎ，ｗｅ ｖｅｒｉｆｙ ｔｈａｔ ｔｈｅ ｕｐｐｅｒ ｂｏｕｎｄ ｉｓ ａｖａｉｌａｂｌｅ ｆｏｒ ｅａｃｈ ｐｏｓｉｔｉｖｅ ｉｎｔｅｇｅｒ竹ａｓ ｗｅｌｌ ａｓ ｔｈｅ ｌｏｗｅｒ ｂｏｕｎｄ ｉｓ ａｖａｉｌａｂｌｅ ｉｆ√元ｉｓ ｐｏｓｉｔｉｖｅ ｉｎｔｅｇｅｒ． Ｋｅｙ ｗｏｒｄｓ：ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈ，ａｌｍｏｓｔ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈ，ｄｉａｍ— ｅｔｅｒ，ｃｈｒｏｍａｔｉｃ ｎｕｍｂｅｒ． ＭＲ ｓ．ｃ．（２０００）：０５Ｃ１２。０５Ｃ１５，０５Ｃ６０ 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的ＥｌＪｇ，Ｊ本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部