论文部分内容阅读
一个图G叫做自补图，如果它与它的补图同构；类似的，一个偶数阶图G叫做几乎自补图，如果G同构与它的一个几乎补图G-M：G≌G-M，其中M为补图G中的一个完美匹配。本文重点研究了自补图和几乎自补图的性质和区别。第三章主要讨论了白补图的直径和色数，并在此基础上，在第四章详细地研究了几乎自补图的性质、直径、色数。证明了连通的几乎自补图的直径只能是2,3，4。并对每一个正整数n≥3，构造了2n阶直径分别为3、4的几乎自补图；对每一个正整数n≥4，构造了2n阶直径为2的几乎自补图。同时，证明了2n阶几乎自补图色数x(G)满足「平方根n]≤x(G<,n>)≤n，通过构造我们证明了不等式的上界是最好的，且当柝为正整数时，下界也是最好的。