The extremal average distance of cubic graphs

讲座名称：The extremal average distance of cubic graphs

讲座人：张晓东 教授

讲座时间：10月11日14:30

地点：腾讯会议直播（ID：343 329 208）

讲座人介绍：

张晓东，上海交通大学数学科学学院教授、博士生导师。1998年6月在中国科学技术大学获得理学博士学位。曾在以色列理工学院(得到Lady Davis Postdoctoral fellowship 资助)和智利大学做博士后、在美国加州大学圣地亚哥分校等校做访问学者。多次主持和参加国家自然科学基金项目。 目前主要研究领域谱图理论、极值图论， 随机图与复杂网络，组合矩阵论等。

讲座内容：

The average distance $\mu(G)$ of a simple connected graph $G$ is the average of the distances between all pairs of vertices in $G$. We prove that for a connected cubic graph $G$ on $n$ vertices, $\mu(G)\le \frac{n^3-16n+48}{4(n^2-n)}$, if $n=4k+2$; and $\mu(G)\le \frac{n^3-32n+128}{4(n^2-n)}$, if $n=4k+4$. Furthermore, all extremal graphs attaining the upper bounds are characterized, and they have the maximum possible diameter. The result solves a question of Plesn\'{\i}k and proves a conjecture of Knor, \v{S}krekovski and Tepeh on the average distance of cubic graphs. The proofs use graph transformations and structural graph analysis. This talk is joined with Yi-Ze Chen, Xin Li (Shanghai Jiao Tong University)

主办单位：数学与统计学院