Kneser图及其导出子图的顶点可分解性质  

Vertex decomposability of Kneser graph and its induced subgraph

作　　者：周思荣 刘阿明 ZHOU Sirong;LIU Aming(School of Mathematics and Statistics,Hainan University,Haikou 570228,China)

机构地区：[1]海南大学数学与统计学院,海南海口570228

出　　处：《海南大学学报(自然科学版中英文)》2025年第1期67-72,共6页Natural Science of Hainan University

基　　金：国家自然科学基金项目(12101165);海南省自然科学基金项目(423RC429)。

摘　　要：Kneser图是十分重要的一类图,许多关于集合的计数以及计算问题可以转换为此类图中的问题加以探讨,在计算机科学、图论、拓扑中都有重要应用。从代数组合方面出发研究Kneser图及其导出子图Schrijver图和交错图的组合代数结构,并完整地刻画了其顶点可分解性质以及Cohen-Macaulay性质。Kneser graph is a very important kind of graph.Many problems related to counting and computing sets can be transformed into the problems in this kind of graph.It is widely used in computer science,graph theory,and topology.In the report,in algebraic combination respect,the combinatorial algebraic structures of Kneser graphs and their induced subgraphs,including Schrijver graphs and interlacing graphs were studied,and their vertex decomposability and Cohen-Macaulay properties were fully characterized.

关 键 词：Kneser图 Schrijver图 交错图 顶点可分解性质 

分 类 号：O157[理学—数学]