完全t-部图的若干研究

大理大学学报 ›› 2026, Vol. 11 ›› Issue (6): 11-18.

完全t-部图的若干研究

1.重庆交通大学土木工程学院，重庆　400074； 2.大理大学数学与计算机学院，云南大理　671003

收稿日期:2025-05-26 出版日期:2026-06-15 发布日期:2026-06-30
通讯作者: 杨利民，教授，博士，E-mail: yanglm65@aliyun.com。
作者简介:杨煌，硕士研究生，主要从事组合数学、图论研究。
基金资助:
大理大学科研发展基金项目（KY2319101540）

Several Studies on Complete t-Partite Graphs

1. School of Civil Engineering, Chongqing Jiaotong University, Chongqing 400074, China; 2. College of Mathematics and Computer
Science, Dali University, Dali, Yunnan 671003, China)

Received:2025-05-26 Online:2026-06-15 Published:2026-06-30

摘要/Abstract

摘要： 文章从7个方面阐述了完全t-部图研究的若干成果和问题及猜想：（1）S（n）-因子的计数；（2）稳定集合分拆的计数；（3）色多项式和单峰性；（4）平均色数；（5）独立数和独立多项式；（6）Hosoya指标和Merrifield-Simmons指标；（7）色唯一性。这些结果丰富了极值图论与代数图论的交叉研究。

关键词: S（n）-因子, 稳定集合, 色多项式, 平均色数, 独立多项式

Abstract: The article presents several achievements, problems, and conjectures in the study of complete t-partite graphs from seven
perspectives: (1) the counting formulas of S(n)-factors; (2) the counting formulas of the partitions of stable sets; (3) chromatic polynomials and unimodality; (4) mean color numbers; (5) independence numbers and independence polynomials; (6) the Hosoya index and the Merrifield-Simmons index; (7) the chromatic uniqueness. These findings enrich the intersection of extremal graph theory and algebraic graph theory.

Key words: S(n)-factor, stable set, chromatic polynomial, mean color number, independence polynomial

中图分类号:

杨　煌, 杨忠燕, 杨利民 . 完全t-部图的若干研究[J]. 大理大学学报, 2026, 11(6): 11-18.

Yang Huang, Yang Zhongyan, Yang Limin. Several Studies on Complete t-Partite Graphs[J]. Journal of Dali University, 2026, 11(6): 11-18.

参考文献

〔1〕杨利民，王天明，年四洪. N [(X1,X2,...,Xi ),k ]的计数公式〔J〕. 大连理工大学学报， 2007， 47（6）：925-930.
〔2〕 YANG L M， WANG T M. The Represnteing Formula of N（G，k）〔J〕. Journal of Combinatorics， Graph Theory and Applications，2026， 1（1）：60-80.
〔3〕 YANG L M， NIAN S H. The Unimodality of N（G，k） and a Combinatorial Identity on Two Kinds Stirling Numbers〔J〕. Far East Journal of Applied Mathematics， 2006， 24（1）：119-128.
〔4〕 YANG L M. Enumeration of Independent Sets of Graphs〔J〕. International Journal of Combinatorial Graph Theory and Applica⁃
tions， 2021， 6（1）：61-69.
〔5〕杨利民，王天明. 色多项式的显示公式〔J〕. 数学进展， 2006， 35（1）：55-66.
〔6〕杨利民，杨娇艳. 稳定集合分拆的伴随多项式和单峰性〔J〕. 大理大学学报， 2024， 9（12）: 1-11.
〔7〕 COMTET L. Advanced Combinatorics: The Art of Finite and Infinite Expansions〔M〕. Dordrecht： Springer Netherlands， 1974.

〔8〕 BONDY J A， MURTY U S R. Graph Theory with Applications〔M〕. London： Macmillan， 1976.

〔9〕 HUH J. Milnor Numbers of Projective Hypersurfaces and the Chromatic Polynomial of Graphs〔J〕. Journal of the American Mathematical Society， 2012， 25（3）： 907-927.
〔10〕杨利民. 理想子图计数及其应用〔J〕. 大连理工大学学报， 1989， 29（5）： 605-609.
〔11〕 YANG L M， WANG T M. The Number of Independent Sets of Windgraphs and the Formula Convolutions of N (-G ,k)〔J〕. Far
East Journal of Mathematical Sciences， 2004， 15（3）：393-404.
〔12〕 YANG L M， NIAN S H. The Number of k Independent Sets of Graphs and the Mean Color Numbers of Graphs〔J〕. International Journal of Combinatorial Graph Theory and Applications， 2021， 6（1）：17-29.
〔13〕杨利民. 图的完全积的独立数和独立多项式〔J〕. 大理大学学报， 2023， 8（6）： 1-8.
〔14〕 LEVIT V E， MANDRESCU E. Independence Polynomials of Well-Covered Graphs： Generic Counterexamples for the Unimodality Conjecture〔J〕. European Journal of Combinatorics， 2006， 27（6）： 931-939.
〔15〕杨利民，段丽燕，王天明. 四叶树Hosoya指标显式公式及其序列〔J〕. 大连理工大学学报， 2016， 56（6）： 657-661.
〔16〕 HUANG Y H. Hoaoya Index and the Matching Defect Polynomials of a graph G without K3 Subgraph〔J〕. Journal of Combinatorics，Graph Theory and Applications， 2026， 1（1）：36-50.
〔17〕徐利民. 关于完全t 部图的色唯一性〔J〕. 运筹与管理， 2007， 16（4）： 61-63.
〔18〕 KOH K M， TEO K L. The Search for Chromatically Unique Graphs〔J〕. Graphs and Combinatorics， 1990， 6（3）： 259-285.
〔19〕 ZHAO H X， LI X L， LIU R Y， et al. The Chromaticity of Certain Complete Multipartite Graphs〔J〕. Graphs and Combinatorics，2004， 20（3）： 423-434.
〔20〕 DURON J， ESPERET L， RAYMOND J F. Long Induced Paths and Forbidden Patterns： Polylogarithmic Bounds〔J〕. SIAM Journal on Discrete Mathematics， 2026， 40（1）： 52-81.

[1]	杨利民, 杨娇艳. 稳定集合分拆的伴随多项式和单峰性[J]. 大理大学学报, 2024, 9(12): 1-11.
[2]	杨利民. 图的完全积的独立数和独立多项式 [J]. 大理大学学报, 2023, 8(6): 1-8.