The Chromatic Equivalence Classes of the Complements of Union Graphs of Vertex and a Path

LI Danyang; MA Haicheng

doi:10.13718/j.cnki.xdzk.2022.04.013

Let G be a graph with order n. It is well known that two graphs G and H are chromatically equivalent if and only if their complementary graphs are adjoint equivalencet. It can be seen that adjoint polynomials are an effective way to study the chromatic polynomials of graphs. By comparing the minimum roots of adjoint polynomials, this paper finally calculates the number of adjoint equivalent graphs of K₁∪P_m and the class of adjoint equivalent graphs are also calculated. Furthermore, the number of chromatic equivalent graphs of K₁∪P_m and the class of chromatic equivalent graphs of K₁∪P_m are also calculated. Here, K₁ and P_m represent an isolated vertex and a path of m vertices, respectively.

HTML

开放科学(资源服务)标识码(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_m₀的补图有相同色划分的图. 本文充分利用伴随等价桥，通过比较两个图伴随多项式最小根的方法得到了集合[$ \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_m₂+1，T_{1，1，m₂-1}.

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

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

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

若H₁=T_{1，1，m₂-1}，利用伴随等价桥(1)和(2)，

从而得到H₂~P_m₂. 再由文献[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_m₂+1，T_{1，1，m₂-1}. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m₂，P_m₂. 由归纳假设和文献[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_m₂+1，T_{1，1，m₂-1}. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m₂，P_m₂. 由归纳假设和文献[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_m₂+1，T_{1，1，m₂-1}. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m₂，P_m₂. 由归纳假设和文献[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_m₂+1，T_{1，1，m₂-1}. 同(ⅰ)类似，我们得到H₂~K₁，K₁∪P_m₂，P_m₂. 由归纳假设和文献[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_m₂+1等价于K₁∪P₃∪D₄∪C₈∪…∪C_m₂+1，再利用等价桥(2)使得图K₁∪P₃∪D₄∪C_m₂+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_m₂+1等价于图P₂∪T_1，1，1∪C₆∪…∪C_m₂+1和T_1，1，1∪P₃∪D₅∪C₁₂∪…∪C_m₂+1.

若m+1=5×2^n-1，K₁∪P_m的等价图除集合Θ₁中的图外，还有集合{K₁∪H：H∈Ω₃}中的图. 由等价桥(2)，{K₁∪H：H∈Ω₃}中的图2K₁∪C₃∪C₅∪…∪C_m₂+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_m₂+1. 由等价桥(9)，集合Θ₁中的图K₁∪P₈∪C₉∪…∪C_m₂+1等价于图P₈∪T_1，1，1∪D₆∪C₁₈∪…∪C_m₂+1.

若m+1=15×2^n-1，n≥2，K₁∪P_m的等价图除集合Θ₁中的图外，还包含图P₁₄∪T_1，1，1∪C₅∪D₇∪C₃₀∪…∪C_m₂+1. 由等价桥(11)，集合Θ₁中的图K₁∪P₁₄∪C₁₅∪…∪C_m₂+1等价于图P₁₄∪T_1，1，1∪C₅∪D₇∪C₃₀∪…∪C_m₂+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所述的每个集合中图的补图构成的集合.

Reference (18)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	CHAO C Y, WHITEHEAD E G J. Chromatically Unique Graphs[J]. Discrete Mathematics, 1979, 27(2): 171-177. doi: 10.1016/0012-365X(79)90107-9 CrossRef Google Scholar
[2]	LIU R Y. A New Method to Find Chromatic Polynomial of Graph and Its Applications[J]. 科学通报(英文版), 1987, 32(21): 1508-1509. Google Scholar
[3]	DONG F M, TEO K L, LITTLE C H C, et al. Chromaticity of Some Families of Dense Graphs[J]. Discrete Mathematics, 2002, 258(1/2/3): 303-321. Google Scholar
[4]	LIU R Y. Adjoint Polynomials and Chromatically Unique Graphs[J]. Discrete Mathematics, 1997, 172(1/2/3): 85-92. Google Scholar
[5]	DU Q Y. Chromaticity of the Complements of Paths and Cycles[J]. Discrete Mathematics, 1996, 162(1/2/3): 109-125. Google Scholar
[6]	WAGNER D G. The Partition Polynomial of a Finite Set System[J]. Journal of Combinatorial Theory(Series A), 1991, 56(1): 138-159. doi: 10.1016/0097-3165(91)90027-E CrossRef Google Scholar
[7]	龚和林, 舒情, 李永明. 一类具有整根色多项式的图的色等价类[J]. 安徽大学学报(自然科学版), 2012, 36(6): 21-25. doi: 10.3969/j.issn.1000-2162.2012.06.005 CrossRef Google Scholar
[8]	DONG F M, KOH K M, TEO K T. Chromatic Polynomials and Chromaticity of Graphs[M]. Singapore: World Scientific, 2005. Google Scholar
[9]	徐利民, 杨志林. 完全3部图K(n-k, n-3, n)色唯一性的证明[J]. 中国科学技术大学学报, 2019, 49(5): 377-381. doi: 10.3969/j.issn.0253-2778.2019.05.004 CrossRef Google Scholar
[10]	魏岭. 一类图的色唯一性[J]. 计算机工程与应用, 2013, 49(22): 52-54. doi: 10.3778/j.issn.1002-8331.1302-0163 CrossRef Google Scholar
[11]	詹福琴, 乔友付. 一类稠密图色唯一的充要条件[J]. 中北大学学报(自然科学版), 2013, 34(1): 10-16. doi: 10.3969/j.issn.1673-3193.2013.01.003 CrossRef Google Scholar
[12]	李雪峰. 某一类色唯一的K₄-同胚图[J]. 数学的实践与认识, 2011, 41(13): 179-184. Google Scholar
[13]	毛建树. $ \overline{T\left( 1, 1, t, 3, 1 \right)}$的色唯一性[J]. 西南师范大学学报(自然科学版), 2010, 35(3): 15-18. Google Scholar
[14]	龚和林, 舒情. 3类具有整根色多项式的色等价类[J]. 西南大学学报(自然科学版), 2011, 33(2): 113-117. Google Scholar
[15]	ZHAO H X, LI X L, ZHANG S G, et al. On the Minimum Real Roots of the σ-Polynomials and Chromatic Uniqueness of Graphs[J]. Discrete Mathematics, 2004, 281(1/2/3): 277-294. Google Scholar
[16]	MA H C, REN H Z. The Chromatic Equivalence Classes of the Complements of Graphs with the Minimum Real Roots of Their Adjoint Polynomials Greater Than-4[J]. Discrete Mathematics, 2008, 308(10): 1830-1836. doi: 10.1016/j.disc.2006.10.020 CrossRef Google Scholar
[17]	YE C F, LI N Z. Graphs with Chromatic Polynomial $ \sum\limits_{l\le {{m}_{0}}}{\left( {matrix} l \\ {{m}_{0}}-l \\ {matrix} \right)}$[J]. Discrete Mathematics, 2002, 259(1): 369-381. Google Scholar
[18]	冶成福. 与K₁∪P_m₀的补图有相同色划分的图[J]. 数学理论与应用, 2002, 22(2): 12-19. Google Scholar

Message Board

The Chromatic Equivalence Classes of the Complements of Union Graphs of Vertex and a Path

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors