|
對一個圖形 G, 我們定義 "獨立指標" 為 G 當中獨立集合的數目;用符
號 i(G) 表示.在參考資料 [3] 當中, Prodinger and Tichy 證明了:
若 T 是一個有 n 個點的樹, 則 f_{n+1}.ltorequ.i(T).ltorequ.
1+2^{n-1},其中 f_{n+1} 是第 n+1 個 Fibonacci 數. 在此論文裡面,我
們要證明:若 F 是一個有 n 個點的森林, 則 f_{n+1}.ltorequ.i(F)
.ltorequ.1+2^n. 另外我們找出上述兩種結果的極限圖形.接著, 對一個
固定的 n, 我們找出一些具有較大獨立指標的 n 個點的樹與森林. 其中
包括一類的樹以及一類的森林. 而這些具有較大獨立指標的 n 個點的樹
其獨立指標是介在 1+2^{n-1} 和 5+2^{n-2} 之間. 另外這些具有較大獨
立指標的 n 個點的森林其獨立指標是介在 2^n 和 1+2^{n-1} 之間.
|