圖的度數對之研究

Abstract

簡單圖G上一點v的平均二度數定義為與v相鄰之點的度數平均。度數列和平均二度數列在最大拉普拉斯特徵值上界的應用，已有許多研究成果。若G中所有點的平均二度數皆為k，則G稱為擬k正則圖。在此論文中，我們證明若G為擬k正則圖，則k是整數；進而找出所有擬正則樹。我們也考慮了當G的最大度數為k^2-k的情形，並給出一些基本的結果。最後，我們對於擬3正則圖給出了更多的結果。並且刻畫出所有十個點之內非正則的擬3正則圖。

Let v be a vertex in a simple graph G. The average 2-degree of v is the average of degrees of vertices adjacent to v. The applications of the degree and average 2-degree sequences on the upper bounds for the maximum eigenvalue of Laplacian matrix of a graph is studied by many authors. The graph G is called pseudo k-regular if each vertex in G has average 2-degree k. We prove that if G is pseudo k-regular then k is integral. Moreover, all pseudo regular trees are given in this thesis. We also consider the case when the maximum degree of G is k2