圖的特徵值最大重覆度與最小路徑分割數之探討

Abstract

G表示一個圖形，我們定義P(G)為最小路徑分割數。而我們定義M（G）所有對應於G圖的對稱方陣之特徵值的最大重覆度。我們研究P（G）和M（G）兩數之間具有的相同性質，並且重證對於任何樹圖T 都滿足P（T）＝M (T)，我們的方法有別於文獻[1]。最後對其它圖G提出一些關於P（G）及M（G）關係的猜測。

Let G be a graph, P ( G ) denote the minimal number of vertex disjoint pathsthat cover all the vertices of G, and M ( G ) denote the maximal multiplicity occuring for an eigenvalue of a symmetric matrix with presscribed graph G. We study the common properties between the two numbers P ( G ) and M ( G ), and reprove P ( T ) = M ( T ) for any trees T, in a di?erent method from [1]. Some conjectures are given in the end of this thesis.