学术预告:Matching extensions and hypercube embeddings of Cayley graphs generated by transpositions

报告题目: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.