報告題目：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.
遼公網安備 21030702000005號
