报告题目：Matching extensions and hypercube embeddings of Cayley graphs generated by transpositions

报告时间：2024年4月12日（星期五）上午9:30-10:30

报告地点：理学院B315

主办单位：理学院

报告人：徐守军

报告人简介：

徐守军，兰州大学数学与统计学院教授，博士生导师。主要研究方向是图论及其应用，离散算法，近似算法，算法复杂性等。2008年-2010年，中科院数学与系统科学研究院从事运筹学方向博士后工作；2010.2-2011.2和2016.9-2017.9, 美国加州大学戴维斯分校计算机系访问两年；2013年6月至9月、2015年12月至2016年1月，香港教育学院访问;目前在SIAM J Discrete Math., Inform. Process. Lett. Discrete Appl. Math, Theor. Comput. Sci., J. Combin. Optim.，Australas. J. Combin.等期刊上发表学术论文。目前主持国家自然科学基金委面上项目一项，主持完成了国家自然科学基金委三项。

报告内容简介：

Let S be a set of transpositions that generates the symmetric group Sn on [n] := {1, 2, . . . , n}, where n > 3. The corresponding Cayley graph is denoted by Cay(Sn, S).

A connected graph G of order at least 2k + 2 is k-extendable for a positive integer k if every matching M of size k can be extended to a perfect matching. The extendability number of G is the maximum k such that Γ is k-extendable. Firstly, we show that Cayley graph Cay(Sn, S) is (|S| − 1)-extendable and determine that the extendability number is |S| − 1 for an integer n > 3.

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. Secondly, we characterize the connected IM-extendable Cayley graphs generated by transpositions, in addition, we give a linear algorithm for checking IM-extendable Cay(Sn,S).

A graph is called a partial cube if it can be embedded into a hypercube isometrically. Finally, we obtain that a Cayley graph Cay(Sn,S) is a partial cube if and only if is a Bubble sort graph.