r个点并圈的补图的色等价图类
The Chromatic Equivalence Classes of the Complements of Union Graphs of r Vertices and a Cycle
DOI: 10.12677/PM.2021.116125, PDF, HTML, 下载: 267  浏览: 347  国家自然科学基金支持
作者: 李丹阳*, 马海成#：青海民族大学数学与统计学院，青海 西宁
关键词: 色多项式；伴随多项式；色等价；伴随等价；色唯一；伴随唯一；Chromatic Polynomial； Adjoint Polynomial； Chromatically Equivalent； Adjointly Equivalent； Chromatically Unique； Adjointly Unique
摘要: 两个图G 和H 色等价当且仅当它们的补图伴随等价. 图G 色唯一当且仅当G 伴随唯一. 在这篇文章中, 我们计算了rK1UCm(r ≥ 1, m ≥ 3) 的伴随等价图的个数, 并刻画了它的伴随等价图类. 因而, 我们也计算了rK1UCm的色等价图的个数, 刻画了rK1UCm的色等价图类.
Abstract: Two graphs G and H are chromatically equivalent if and only if G and H are adjointly equivalent. G is chromatically unique if and only if G adjointly unique. In this paper, the number of the adjoint equivalence graphs of rK1UCm(r ≥ 1, m ≥ 3) is calculated, and the adjoint equivalence classes of rK1UCm can also be characterized. As a result, the number of the chromatic equivalence graphs of rK1UCm is calculated, and the chromatic equivalence classes of rK1UCm can also be characterized.
文章引用：李丹阳, 马海成. r个点并圈的补图的色等价图类[J]. 理论数学, 2021, 11(6): 1112-1120. https://doi.org/10.12677/PM.2021.116125

参考文献

[1] Liu, R.Y. (1997) Adjoint Polynomials and Chromatically Unique Graphs. Discrete Mathemat- ics, 172, 85-92.
https://doi.org/10.1016/S0012-365X(96)00271-3
[2] Dong, F.M., Koh, K.M. and Teo, K.T. (2005) Chromatic Polynomials and Chromaticity of Graph. World Scientific, London.
[3] Liu, R.Y. (1987) A New Method to Find Chromatic Polynomial of Graph and Its Applications. Chinese Science Bulletin, 32, 1508-1509. (In Chinese, English Summary)
[4] Zhao, H., Huo, B. and Liu, R. (2000) Chromaticity of the Complements of Paths. Journal of Mathematical Study, 33, 345-353.
[5] Ye, C.F. and Li, N.Z. (2002) Graphs with Chromatic Polynomial ？ 1≤m0 lm0 − 1(λ)l. Discrete Mathematics, 259, 369-381.
https://doi.org/10.1016/S0012-365X(02)00592-7
[6] Zhao, H.X., Li, X.L., Zhang, S.G. and Liu, R.Y. (2004) On the Minimum Real Roots of the σ-Polynomials and Chromatic Uniqueness of Graphs. Discrete Mathematics, 281, 277-294.
https://doi.org/10.1016/j.disc.2003.06.010
[7] Ye, C.F. and Yang, W.J. (2004) The Graphs with the Same Chromatic Partitions as the Complement of T1,2,n. Journal of Northeast Normal University, 36, 18-26.
[8] Dong, F.M., Teo, K.L., Little, C.H.C. and Hendy, M.D. (2002) Chromaticity of Some Families of Dense Graphs. Discrete Mathematics, 258, 303-321.
https://doi.org/10.1016/S0012-365X(02)00355-2
[9] Ma, H.C. and Ren, H.Z. (2008) The Chromatic Equivalence Classes of the Complements of Graphs with the Minimum Real Roots of Their Adjoint Polynomials Greater Than –4. Discrete Mathematics, 308, 1830-1836.
[10] Du, Q.Y. (1996) Chromaticity of the Complements of Paths and Cycles. Discrete Mathematics, 162, 109-125.
https://doi.org/10.1016/0012-365X(95)00308-J

为你推荐