开放科学(资源服务)标识码(OSID):

本文仅考虑有限无向的简单图. 对于图G，令G，V(G)，E(G)，χ(G)分别为图G的补图、点集、边集、色数. K_n，P_n和C_n(n≥3)分别表示n个点的完全图、路和圈. K₁表示一个孤立点. D_n表示C₃上的一点与路P_n-2的一个端点黏结后得到的图. T_i，j，k表示只有1个3度点，3个1度点，且这个3度点到3个1度点的距离分别为i，j，k的树. N_G(v)表示G中所有与点v邻接的点构成的集合. G∪Hb1表示图G与图H的不交并，mG表示m个G的不交并.

设G是一个n阶图. 用λ种颜色对图G的顶点进行着色，使得相邻顶点着不同色的方法数是λ的一个多项式，被称为图G的色多项式，记为P(G，λ). 若两个图G和H的色多项式相等，则称这两个图是色等价的，记为G~_PH，与图G色等价的所有图构成的集合记为[G]_p，称为图G的色等价图类. 若与图G色等价的任何图H均有H$ \cong $G，即[G]_p={G}，则称图G是色唯一的. 文献[1]首次定义了图的色等价和色唯一的概念. 为了研究图的色多项式，文献[2]提出了伴随多项式的概念，如果P(G，λ)=$ \sum\limits_{i=1}^{n}{\alpha \left( \bar{G}, i \right)}$(λ)_i为图G的补图G的色多项式，则

称为图G的伴随多项式，这里的(λ)_i=λ(λ-1)…(λ-i+1). 到目前为止，关于这方面已经有了大量的研究成果^[3-8]. 若两个图G和H的伴随多项式相等，则称这两个图是伴随等价的，记为G~H. 与图G伴随等价的所有图构成的集合记为[G]. 若与图G伴随等价的任何图H均有H$ \cong $G，则称图G是伴随唯一的. 由伴随多项式和色多项式之间的关系容易发现：两个图G和H色等价当且仅当它们的补图伴随等价，图G色唯一当且仅当它的补图伴随唯一. 利用伴随多项式研究图的色性这方面已有了大量的结果^[9-18]. 用β(G)表示伴随多项式h(G，x)的最小实根. 文献[15]得到了β(G)＞-4的所有图G. 文献[16]给出了β(G)＞-4的所有图之间伴随等价的一个规律，且给出了其中两个图之间变化的12个伴随等价关系，称为伴随等价桥. 然而，对于给定的图G，完全确定集合[G]_p是很困难的. 文献[17]确定了集合[P_m]_p，文献[18]得到了与K₁∪P_m0的补图有相同色划分的图. 本文充分利用伴随等价桥，通过比较两个图伴随多项式最小根的方法得到了集合[$ \overline{{{K}_{1}}\cup {{P}_{m}}}$]，因此也得到了集合[$ \overline{{{K}_{1}}\cup {{P}_{m}}}$]_p.

为了找到K₁∪P_m(m≥2)的所有伴随等价图，按m+1所含的最大奇因数是1，3，5，9，15或其他奇数分为6种情形. 为方便，用δ(G)表示图G的所有不同构的伴随等价图的个数. δ(G)=1当且仅当G是伴随唯一的. 为方便读者阅读，下面列出文献[16]中的12个等价桥：

(1) P_2m+1~P_m∪C_m+1(m≥3)；

(2) T_1，1，n~K₁∪C_n+2(n≥2)；

(3) T_1，2，n~K₁∪D_n+3；

(4) P₄~K₁∪C₃；

(5) K₁∪P₅~P₂∪T_1，1，1；

(6) C₄~D₄；

(7) P₂∪C₆~P₃∪D₅；

(8) P₂∪C₉~P₅∪D₆；

(9) K₁∪C₉~T_1，1，1∪D₆；

(10) P₂∪C₁₅~P₅∪C₅∪D₇；

(11) K₁∪C₁₅~T_1，1，1∪C₅∪D₇；

(12) C₁₅∪D₆~C₅∪C₉∪D₇.

定理1  (ⅰ)若m+1=2ⁿ⁺¹对某个正整数n成立，则

(ⅱ) 若m+1=3×2^n-1对某个正整数n成立，则

(ⅲ) 若m+1=5×2^n-1对某个正整数n成立，则

(ⅳ) 若m+1=9×2^n-1对某个正整数n成立，则

(ⅴ) 若m+1=15×2^n-1对某个正整数n成立，则

(ⅵ) 若m+1=2^n-1(2k+1)对某对正整数n，k(≠1，2，4，7)成立，则

证  设H~K₁∪P_m，H₁是H的一个连通分支，使得β(H₁)=β(P_m)，H=H₁∪H₂.

(ⅰ) 当n=1时，由文献[16]中的推论3.2知K₁∪P₃是伴随唯一的. 对n≥2用数学归纳法. 当n=2时，比较两边的最小实根，由文献[16]中的引理2.7知H₁=P₇，C₄，D₄，T_1，1，2.

若H₁=P₇，由K₁∪P₇~H=P₇∪H₂得H₂~K₁，由K₁伴随唯一得到H₂= K₁.

若H₁=C₄，利用伴随等价桥(1)，H=C₄∪H₂~K₁∪P₇~K₁∪P₃∪C₄，从而得到H₂~K₁∪P₃，再由文献[16]中的推论3.2知K₁∪P₃伴随唯一，所以H₂=K₁∪P₃.

若H₁=D₄，利用伴随等价桥(1)和(6)，H=D₄∪H₂~K₁∪P₇~K₁∪P₃∪D₄，从而得到H₂=K₁∪P₃.

若H₁=T_1，1，2，利用伴随等价桥(1)和(2)，H=T_1，1，2∪H₂~K₁∪P₇~K₁∪P₃∪C₄~P₃∪T_1，1，2，从而得到H₂= P₃. 故δ(K₁∪P₇)=4.

假设结论对n-1(n≥3)，即m′+1=2ⁿ成立. 由文献[16]中的引理2.7知H₁=P_m，C_m2+1，T_1，1，m2-1.

若H₁=P_m，由K₁∪P_m~H=P_m∪H₂，得H₂=K₁.

若H₁=C_m2+1，利用伴随等价桥(1)，

从而得到H₂~K₁∪P_m2. 由归纳假设，这样的H₂共有$ \frac{\left( n-1 \right)\left( n+2 \right)}{2}$-1个.

若H₁=T_1，1，m2-1，利用伴随等价桥(1)和(2)，

从而得到H₂~P_m2. 再由文献[17]中的定理1知这样的H₂共有n个.

故

(ⅱ) 当n=1时，由文献[16]中的推论3.2知K₁∪P₂是伴随唯一的. 当n=2时，由文献[16]中的引理2.7知H₁=P₅，T_1，1，1，相应地，H₂~K₁或H₂~P₂，进一步得到H₂= K₁，P₂. 故δ(K₁∪P₅)=2. 对n≥3用数学归纳法. 当n=3时，由文献[16]中的引理2.7知H₁=P₁₁，C₆，T_1，1，4，D₅，T_1，2，2.

若H₁=P₁₁，由H=P₁₁∪H₂~K₁∪P₁₁得H₂=K₁.

若H₁=C₆，利用伴随等价桥(1)，H=C₆∪H₂~K₁∪P₁₁~K₁∪P₅∪C₆，得H₂~K₁∪P₅，又由n=2的情形知H₂=K₁∪P₅，P₂∪T_1，1，1.

若H₁=T_1，1，4，利用伴随等价桥(1)和(2)，H=T_1，1，4∪H₂~K₁∪P₁₁~K₁∪P₅∪C₆~P₅∪T_1，1，4，从而得到H₂~P₅，由文献[16]中的推论3.2知P₅是伴随唯一的，所以H₂=P₅.

若H₁=D₅，利用伴随等价桥(1)，(5)和(7)，H=D₅∪H₂~K₁∪P₁₁~K₁∪P₅∪C₆~P₂∪T_1，1，1∪C₆~P₃∪D₅∪T_1，1，1，从而得到H₂~P₃∪T_1，1，1，又由文献[16]中的推论3.2知P₃∪T_1，1，1是伴随唯一的，所以H₂=P₃∪T_1，1，1.

若H₁=T_1，2，2，利用伴随等价桥(1)，(3)和(7)，H=T_1，2，2∪H₂~K₁∪D₅∪H₂~K₁∪P₁₁~K₁∪P₅∪C₆~P₂∪T_1，1，1∪C₆~P₃∪D₅∪T_1，1，1，从而得到K₁∪H₂~P₃∪T_1，1，1，由于P₃∪T_1，1，1是伴随唯一的，所以这样的H₂是不存在的. 故δ(K₁∪P₁₁)=5.

假设结论对n-1(n≥3)，即m′+1=3×2^n-2成立. 由文献[16]中的引理2.7知H₁=P_m，C_m2+1，T_1，1，m2-1. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m2，P_m2. 由归纳假设和文献[17]中的定理1知，这样的H₂分别有1个，$ \frac{\left( n-1 \right)\left( n-2 \right)}{2}$+2个或n-2个，故

(ⅲ) 当n=1时，由文献[16]中的引理2.7知H₁=P₄，C₃，相应地，H₂~K₁，2K₁，进一步，H₂= K₁，2K₁. 故δ(K₁∪P₄)=2. 对n≥2用数学归纳法. 当n=2时，由文献[16]中的引理2.7知H₁=P₉，C₅，T_1，1，3.

若H₁=P₉，由H=P₉∪H₂~K₁∪P₉得H₂=K₁.

H₁=C₅，利用伴随等价桥(1)，H=C₅∪H₂~K₁∪P₉~K₁∪P₄∪C₅，得H₂~K₁∪P₄，又由n=1的情形知H₂=K₁∪P₄，2K₁∪C₃.

若H₁=T_1，1，3，利用伴随等价桥(1)和(2)，H=T_1，1，3∪H₂~K₁∪P₉~K₁∪P₄∪C₅~P₄∪T_1，1，3，得H₂~P₄，又由文献[17]中的定理1得H₂=P₄，K₁∪C₃. 故δ(K₁∪P₉)=5.

假设结论对n-1(n≥3)，即m′+1=5×2^n-2成立. 由文献[16]中的引理2.7知H₁=P_m，C_m2+1，T_1，1，m2-1. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m2，P_m2. 由归纳假设和文献[17]中的定理1知，这样的H₂分别有1个，(n-1)²+1个或2(n-1)个，故

(ⅳ) 当n=1时，由文献[16]中的推论3.2知K₁∪P₈是伴随唯一的. 对n≥2用数学归纳法. 当n=2时，由文献[16]中的引理2.7知H₁=P₁₇，C₉，T_1，1，7，D₆，T_1，2，3.

若H₁是前4个图，相应地，H₂~K₁，K₁∪P₈，P₈，P₈∪T_1，1，1，由文献[16]中的推论3.2知这些图都是伴随唯一的，所以H₂=K₁，K₁∪P₈，P₈，P₈∪T_1，1，1.

若H₁=T_1，2，3，利用伴随等价桥(1)，(3)和(9)，H=T_1，2，3∪H₂~K₁∪D₆∪H₂~K₁∪P₁₇~K₁∪P₈∪C₉~P₈∪T_1，1，1∪D₆，得K₁∪H₂~P₈∪T_1，1，1，又由于P₈∪T_1，1，1是伴随唯一的，所以这样的H₂是不存在的. 故δ(K₁∪P₁₇)=4.

假设结论对n-1(n≥3)，即m′+1=9×2^n-2成立. 由文献[16]中的引理2.7知H₁=P_m，C_m2+1，T_1，1，m2-1. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m2，P_m2. 由归纳假设和文献[17]中的定理1知，这样的H₂分别有1个，$ \frac{n\left(n-1 \right)}{2}$+1个或n-1个，故

(ⅴ) 证明与(ⅳ)类似.

(ⅵ) 对n≥1用数学归纳法. 当n=1时，由文献[16]中的推论3.2知K₁∪P_2k是伴随唯一的. 假设结论对n-1(n≥3)，即m′+1=2^n-2×(2k+1)(k≠1，2，4，7)成立. 由文献[16]中的引理2.7知H₁=P_m，C_m2+1，T_1，1，m2-1. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m2，P_m2. 由归纳假设和文献[17]中的定理1知，这样的H₂分别有1个，$ \frac{n\left( n-1 \right)}{2}$个或n-1个，故

若m+1=2ⁿ⁺¹对某个正整数n成立，或m+1=2^n-1×(2k-1)(k≠2)对某对正整数n，k成立，令

若m+1=3×2^n-1对某个正整数n成立，令

若m+1=5×2^n-1对某个正整数n成立，令

这里的m₁=m，m_i+1= $ \frac{{{m}_{i}}-1}{2}$(i=1，2，…，n-1)，集合Ω₁，Ω₂和Ω₃分别有n，n-1和n个图. 文献[17]确定了集合[P_m]如下：

若m+1=2ⁿ⁺¹对某个正整数n成立，则

若m+1=3×2^n-1对某个正整数n成立，则

若m+1=5×2^n-1对某个正整数n成立，则[P_m]=Ω₁∪Ω₃；

若m+1=2^n-1×(2k+1)(k≠1，2)对某对正整数n和k成立，则[P_m]=Ω₁.

若m+1=2ⁿ⁺¹对某个正整数n成立，或m+1=2^n-1×(2k-1)(k≠2)对某对正整数n，k成立，由等价桥(2)我们知道，集合Ω₁中的每一个含有圈分支的图中的每一个圈与一个孤立点K₁相遇就会等价于一个T-形分支. 令

它就是集合Ω₁中的每一个含有圈分支的图中的一个圈与一个孤立点K₁相遇等价于一个T-形分支后形成的集合，所以Φ₁中共有$ \left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)$个图. 令Θ₁={K₁∪H：H∈Ω₁}∪Φ₁，则|Θ₁|= $ \left( \begin{matrix} { n+1} \\ 2 \\ \end{matrix} \right)$.

若m+1=2ⁿ⁺¹对某个正整数n成立，由等价桥(6)，Θ₁中的图K₁∪P₃∪C₄∪C₈∪…∪C_m2+1等价于K₁∪P₃∪D₄∪C₈∪…∪C_m2+1，再利用等价桥(2)使得图K₁∪P₃∪D₄∪C_m2+1∪…∪C_mn-1+1中的每一个圈分支与一个孤立点K₁相遇就会等价于一个T-形分支，令

则Δ₁中共有$ \left( {\begin{array}{*{20}{c}} {n - 1}\\ 1 \end{array}} \right)$个图.

若m+1=3×2^n-1，n≥3. 由等价桥(2)知集合Ω₂中的每一个含有圈分支的图中的每一个圈与一个孤立点K₁相遇就会等价于一个T-形分支. 令

它就是集合Ω₂中每一个含有圈分支的图中的一个圈与一个孤立点K₁相遇等价于一个T-形分支后形成的集合，所以Φ₂中共有$ \left( {\begin{array}{*{20}{c}} {n - 1}\\ 2 \end{array}} \right)$个图. 令Θ₂={K₁∪H：H∈Ω₂}∪Φ₂，则|Θ₂|= $ \left( {\begin{array}{*{20}{c}} {n }\\ 2 \end{array}} \right)$. 另外，由等价桥(5)，集合Θ₂中的图K₁∪P₅∪C₆∪…∪C_m2+1等价于图P₂∪T_1，1，1∪C₆∪…∪C_m2+1和T_1，1，1∪P₃∪D₅∪C₁₂∪…∪C_m2+1.

若m+1=5×2^n-1，K₁∪P_m的等价图除集合Θ₁中的图外，还有集合{K₁∪H：H∈Ω₃}中的图. 由等价桥(2)，{K₁∪H：H∈Ω₃}中的图2K₁∪C₃∪C₅∪…∪C_m2+1中除C₃外的任何两个圈与两个孤立点2K₁相遇就会等价于两个T-形分支. 令

则Δ₂中共有$ \left( {\begin{array}{*{20}{c}} {n - 1}\\ 2 \end{array}} \right)$个图.

若m+1=9×2^n-1，n≥2，K₁∪P_m的等价图除集合Θ₁中的图外，还包含图P₈∪T_1，1，1∪D₆∪C₁₈∪…∪C_m2+1. 由等价桥(9)，集合Θ₁中的图K₁∪P₈∪C₉∪…∪C_m2+1等价于图P₈∪T_1，1，1∪D₆∪C₁₈∪…∪C_m2+1.

若m+1=15×2^n-1，n≥2，K₁∪P_m的等价图除集合Θ₁中的图外，还包含图P₁₄∪T_1，1，1∪C₅∪D₇∪C₃₀∪…∪C_m2+1. 由等价桥(11)，集合Θ₁中的图K₁∪P₁₄∪C₁₅∪…∪C_m2+1等价于图P₁₄∪T_1，1，1∪C₅∪D₇∪C₃₀∪…∪C_m2+1.

于是，我们得到下面的结果：

定理2  (ⅰ) 若m+1=2ⁿ⁺¹对某个正整数n成立，则

(ⅱ) 若m+1=3×2^n-1对某个正整数n成立，则

(ⅲ) 若m+1=5×2^n-1对某个正整数n成立，则

(ⅳ) 若m+1=9×2^n-1对某个正整数n成立，则

(ⅴ) 若m+1=15×2^n-1对某个正整数n成立，则

(ⅵ) 若m+1=2^n-1(2k+1)对某对正整数n，k(≠1，2，4，7)成立，则[K₁∪P_m]=Θ₁.

证  由文献[16]中的等价变换规律，这些图均等价于K₁∪P_m，且图的个数也等于δ(K₁∪P_m).

推论1  对于定理2中m的不同类型，[K₁∪P_m]_P就是定理2所述的每个集合中图的补图构成的集合.