报告名称：Matching extensions and Hypercube embeddings of Cayley graphs generated by transpositions

报告专家：冯永锝

专家所在单位：新疆大学

报告时间：2024年6月15日11:00-12:00

报告地点: 永利集团88304官网204会议室

专家简介：冯永锝，博士，新疆大学数学与系统科学学院副研究员，硕士生导师，近年来主要从事图论中和匹配相关, 图的着色,组合优化与算法等方面的研究。目前在J. Graph Theory，Discrete Math.，Discrete Appl.Math，Filomat 等重要期刊上发表论文20余篇，参与承担国家自然科学基金项目2项。

报告摘要：A connected graph Γ with a perfect matching of order at least 2k+2 is said to be kextendable if for every matching M of k edges can be extended to a perfect matching of Γ. The extendability number of Γ is the maximum integer k such that Γ is k-extendable. Let S be a subset of transpositions and generate n−element symmetry group S��. Firstly,   we determine the extendability number of  connected Cay(S��,S).   Secondly, we characterize a connected IM-extendable Cay(S��,S). A graph is called a partial cube if it can be embedded into a hypercube isometrically.

Finally, we  show that a connected Cay(S��,S) is a partial cube if and only if Γ is a bubble sort graph.