Maximizing the algebraic connectivity of a graph of given order and size

图的代数连通性是一个与图的连通性和扩展性密切相关的图不变量。给定n和m，定义f(n,m)为具有n个顶点和m条边的图的最大代数连通性。已知具有n个顶点的树的最大代数连通性为1，且由星图达到，即f(n,n−1)=1。

具有两个部分集（大小分别为2和n−2）的完全二分图的代数连通性等于2。2015年，Kolokolnikov猜想当n>3时f(n,2n−4)=2，并通过计算验证了该猜想在n较小的情形成立。本报告将介绍关于该猜想及相关极值图论问题的最新进展。

Prof. Sebastian M. Cioaba，美国特拉华大学数学科学系教授。