The Number of Independent Sets in Forests Having no Isolated Vertices with a Given Size

給定邊數且不具孤立點之林圖獨立集個數

周敏貞(Min-Jen Jou) ； 林正忠(Jeng-Jong Lin)

《嶺東學報》 29期 (2011/06) Pp. 127-132

https://doi.org/10.29850/LTJ.201106.0006

摘要

圖形G=(V, E)中之獨立集爲點集V之一子集合S，且使得S中任兩點在G中均不相連。令F(下標 m)爲具有m條邊且不具孤立點所有林圖所成的集合。在本篇論文中，我們確定了F(下標 m)中獨立集之第一、第二及第三大數值。除此之外，我們亦描繪出達到這些數值之極圖。

關鍵字

獨立集 ； 孤立點 ； 林圖 ； 極圖

並列摘要

In a graph G=(V, E), an independent set is a subset S of V such that no two vertices in S are adjacent. Let F(subscript m) denote the set of forests of size m having no isolated vertices. In this paper, the forests in F(subscript m) with the largest, the second largest and the third largest numbers of independent sets are determined, respectively. We also characterize those extremal graphs achieving these values.

並列關鍵字

independent set ； isolated vertex ； forest ； extremal graph

參考文獻

Jou, M.-J(1996).Counting independent sets.Department of Applied Mathematics of National Chiao Tung University.

(M.-J. Jou, Independent sets in trees, to appear in Ars Combinatoria.).

Knopfmacher, A.,Tichy, R. F.,Wagner, S.,Ziegler, V.(2007).Graphs, partitions and Fibonacci numbers.Discrete Appl. Math.155,1175-1187.

Li, S.,Zhu, Z.(2009).The number of independent sets in unicyclic graphs with a given diameter.Discrete Appl. Math.157,1387-1395.

Lin, S. B.,Lin, C.(1995).Trees and forests with large and small independent indices.Chinese J. Math.23,199-210.