Forests with the Third Largest Number of Maximal Independent Sets

林圖中最大獨立集之第三大數值

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

《嶺東學報》 27期 (2010/06) Pp. 203-211

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

摘要

G=(V, E)爲一簡單且無方向圖形。圖形G之獨立集爲點集V之一子集合S，且使得S中任兩點在G中均不相連。若一獨立集不爲其他獨立集之真子集，則稱此獨立集爲最大獨立集。在本篇論文中，我們確定了林圖中最大獨立集之第三大數值。除此之外，我們亦描繪出達到此值之所有極圖。

關鍵字

獨立集 ； 最大獨立集 ； 林圖 ； 極圖

並列摘要

Let G = (V, E) be a simple undirected graph. An independent set is a subset S of V such that no two vertices in S are adjacent. A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the third largest number of maximal independent sets among all forests. We also characterize those extremal graphs achieving this value.

並列關鍵字

independent sets ； maximal independent sets ； trees ； forests ； extremal graphs

參考文獻

Jou, M. J.,Lin, J. J.(2009).Trees with the second largest number of maximal independent sets.Discrete Math.309,4469-4474.

Jin, Z.,Li, X.(2008).Graphs with the second largest number of maximal independent sets.Discrete Math.308,5864-5870.

Jin, Z.,Yan, H. F.(2009).Trees with the second and third largest number of maximal independent sets.Ars Combin.93,341-351.

Jou, M. J.(1991).The number of maximal independent sets in graphs.Department of Mathematics, National Central University.

Jou, M. J.,Chang, G. J.(1997).Maximal independent sets in graphs with at most one cycle.Dicrete Appl. Math.79,67-73.