圖上的曲率及相關問題

Abstract

2022年，Steinerberger在圖上定義了一個曲率的概念，這個定義和圖的距離矩陣有關。在這篇論文，我們介紹Steinerberger曲率[27]、探討另一個他的相關研究[26]，並提供新的結果。我們刻畫在經過圖操作後的距離矩陣，這些操作包括在兩個圖加入一條邊連接、在兩個圖在一個點合併，和在一個圖移除一個橋。我們證明了如果一個圖有正曲率，在這些操作下，新的圖除了至多兩個點外會有正曲率。若D是圖的距離矩陣，我們提供了一個方法來建構圖使得Dx = 1無解。最後，若v是一個樹的距離矩陣最大特徵值的特徵向量，且其元都為正，我們提供了一個和葉子個數有關的⟨v, 1⟩的下界估計。

In 2022, Steinerberger proposed a notion of curvature on graphs involving the graph distance matrix. In this thesis, we give a survey of his works [26, 27] and extend further results. We characterize the distance matrices when certain graph operations are applied, such as adding an edge between two graphs, merging two graphs at a vertex, or removing a bridge from a graph. We show that positive curvatures are preserved except for one or two vertices under these graph operations. Let D be the distance matrix of a graph. We provide a method to construct graphs with the property that Dx = 1 has no solution. Finally, let v be the first eigenvector of the distance matrix of a tree with positive entries, as guaranteed by the Perron-Frobienius theorem. We provide a lower bound of ⟨v, 1⟩ involving the number of leaves.