講座名稱：The extremal average distance of cubic graphs

講座人：張曉東 教授

講座時(shí)間：10月11日14:30

地點(diǎn)：騰訊會(huì)議直播（ID：343 329 208）

講座人介紹：

張曉東，上海交通大學(xué)數(shù)學(xué)科學(xué)學(xué)院教授、博士生導(dǎo)師。1998年6月在中國(guó)科學(xué)技術(shù)大學(xué)獲得理學(xué)博士學(xué)位。曾在以色列理工學(xué)院(得到Lady Davis Postdoctoral fellowship 資助)和智利大學(xué)做博士后、在美國(guó)加州大學(xué)圣地亞哥分校等校做訪問學(xué)者。多次主持和參加國(guó)家自然科學(xué)基金項(xiàng)目。 目前主要研究領(lǐng)域譜圖理論、極值圖論， 隨機(jī)圖與復(fù)雜網(wǎng)絡(luò)，組合矩陣論等。

講座內(nèi)容：

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)

主辦單位：數(shù)學(xué)與統(tǒng)計(jì)學(xué)院