東北大学 大学院情報科学研究科
純粋・応用数学研究センター

組合せ論セミナー

第54回 2014年7月18日 14:30〜16:00

山田 紘頌(名古屋大学)「On a remark of Graham and Lovász on the signature of distance matrices of graphs (連結グラフの距離符号数に関するGraham-Lovászの問題について)」

Graham and Lovász (1978) remarked that it is not known whether a graph exists such that the number of positive eigenvalues of its distance matrix is greater than that of negative eigenvalues. In this talk, I discuss the equality case of their problem. I present the smallest example with some remarks, and show such examples can be obtained from combinatorial 2-designs.

Graham-Lovász (1978) は連結グラフの距離行列について, その正の固有値の個数が負の固有値の個数より多いグラフは存在するか, という問題を提示した. 本セミナーでは, 特にこの問題の等号成立の場合について考察する. まず最小の例について紹介し, ある2-デザインの構造からその無限系列が得られることを示す.