In July 2012, at the Conference on Applications of Graph Spectra in Computer Science, Barcelona, D. Stevanovic posed the following open problem: which graphs have the zero as the largest eigenvalue of their modularity matrix? The conjecture was that only the complete and complete multipartite graphs. They indeed have this property, but are they the only ones? In this paper, we will give an affirmative answer to this question and prove a bit more: both the modularity and the normalized modularity matrix of a graph is negative semidefinite if and only if the graph is complete or complete multipartite.
翻译:在2012年7月于巴塞罗那举行的计算机科学应用图谱会议上,D.Stevanovic提出了以下尚未解决的问题:哪些图的零是其模块矩阵的最大半成值?假设是只有完整和完整的多部分图。它们确实具有这一属性,但是否是唯一的图?在本文件中,我们将对这一问题给出一个肯定的答案,并证明更多一点:一个图的模块化和标准模块化矩阵都是负半成型的,如果并且只有在图表是完整或完整的多部分图时。