A graph G is said to be determined by the generalized spectrum (DGS) if, for any graph H, whenever H and G are cospectral and their complements are also cospectral, then H is isomorphic to G. Existing methods for proving the DGS property of graphs are invalid for highly uncontrollable graphs. To address this problem, in this talk we propose a novel method to verify that certain uncontrollable graphs are DGS, which is established upon a newly discovered relation between the DGS property of a line graph and that of its root graph.

王卫，西安交通大学数学与统计学院教授、博士生导师。主要研究领域为代数图论与组合最优化。在图谱理论的研究中对图的广义谱刻画问题做出了一些原创性的工作，在组合优化领域中对一些NP-困难组合优化问题设计出了一些好的近似算法。在J. Combin. Theory, Ser B, European J.Combin. 以及IEEE/ACM Transactions系列等组合图论刊物上发表研究论文100余篇，主持（完成）国家自然科学基金面上项目多项。目前担任中国运筹学会图论与组合分会常务理事、陕西省工业与应用数学学会理事长及国际刊物“Linear Algebra Appl.”“Discrete Mathematics, Algorithms and Applications”编委等。