澳门永利赌场龙-澳门永利赌场现况-网上赌博网址

報(bào)告題目：Matching extensions and hypercube embeddings of Cayley graphs generated by transpositions

報(bào)告時(shí)間：2024年4月12日（星期五）上午9:30-10:30

報(bào)告地點(diǎn)：理學(xué)院B315

主辦單位：理學(xué)院

報(bào)告人：徐守軍

報(bào)告人簡(jiǎn)介：

徐守軍，蘭州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院教授，博士生導(dǎo)師。主要研究方向是圖論及其應(yīng)用，離散算法，近似算法，算法復(fù)雜性等。2008年-2010年，中科院數(shù)學(xué)與系統(tǒng)科學(xué)研究院從事運(yùn)籌學(xué)方向博士后工作；2010.2-2011.2和2016.9-2017.9, 美國(guó)加州大學(xué)戴維斯分校計(jì)算機(jī)系訪(fǎng)問(wèn)兩年；2013年6月至9月、2015年12月至2016年1月，香港教育學(xué)院訪(fǎng)問(wèn);目前在SIAM J Discrete Math., Inform. Process. Lett. Discrete Appl. Math, Theor. Comput. Sci., J. Combin. Optim.，Australas. J. Combin.等期刊上發(fā)表學(xué)術(shù)論文。目前主持國(guó)家自然科學(xué)基金委面上項(xiàng)目一項(xiàng)，主持完成了國(guó)家自然科學(xué)基金委三項(xiàng)。

報(bào)告內(nèi)容簡(jiǎn)介：

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.