报告人：宁博博士，天津大学

报告时间：2016年11月11日15:30点

报告地点：数计学院4号楼229室

报告题目：Two problems on cycles in graphs

报告摘要：Our talk includes two topics from structural graph theory. In particular, it is closely related to two previous papers of Fan.

In 1984, Fan proved that every 2-connected graph $G$ is Hamiltonian if every two vertices $x,y$ of distance two in $G$ satisfy that $\\max\\{d(x),d(y)\\}\\geq \\frac{|G|}{2}$, which is called Fan-Theorem in many papers and monographs. Our first purpose of this talk is to present a complete characterization of (so called) Fan-type heavy subgraph pairs $\\{R,S\\}$ such that a 2-connected graph is Hamiltonian if it is $\\{R,S\\}$-f-heavy.

In 1990, generalizing a famous theorem of Erd\\H{o}s and Gallai, Fan proved that for every two distinct vertices $x,z$ in a 2-connected graph $G$, there is an $(x,z)$-path of length at least the average degree of all vertices other than $x$ and $z$ in $G$.Our second purpose of this talk is to present an extension of Fan's theorem. We prove that for any two vertices $x,z$ in a $k$-connected graph $G$ and every vertex set $Y\\subseteq V(G)\\backslash \\{x,z\\}$ with $|Y|=k-2$, there is an $(x,Y,z)$-path of length at least the average degree of all vertices other than $x$ and $z$ in $G$.

欢迎老师和研究生参加！