题名

The number of maximal independent sets in triangle-free quasi-tree graphs

并列篇名

無3迴圈準樹圖中最大獨立集之個數

作者

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

关键词

最大獨立集 ； 無3 迴圈 ； 樹圖 ； 林圖 ； 準樹圖 ； 準林圖 ； 極圖 ； maximal independent set ； triangle-free ； tree ； forest ； quasi-tree graph ； quasi-forest graph ； extremal graph

期刊名称

嶺東學報

卷期/出版年月

39期（2016 / 06 / 01）

页次

75 - 93

内容语文

英文
中文摘要

若一獨立集不為其他獨立集之真子集，則稱此獨立集為最大獨立集。一個具有點集V (G) 的連通圖形G（圖形G），若存在點x ∈V (G) 使得G-x 為樹圖（林圖），則稱G 為準樹圖（準林圖）。本篇論文目的在於找到了所有不具有邊數為3 之迴圈的準樹圖（準林圖）中最大獨立集之最大數值。除此之外，我們亦描繪出達到此值之所有極圖。
英文摘要

A maximal independent set is an independent set that is not a proper subset of any other independent set. A connected graph (respectively, graph) G with vertex set V(G) is called a quasi -tree graph (respectively, quasi-forest graph), if there exists a vertex x ∈V ( G) such that G - x is a tree (respectively, forest) . The purpose of this paper is to determine the largest number of maximal independent sets among all quasi- tree graphs and quasi -forest graphs containing no cycle of length three, respectively. Additionally, extremal graphs achieving these values are also given.
主题分类 人文學 > 人文學綜合
人文學 > 歷史學
基礎與應用科學 > 資訊科學
社會科學 > 社會科學綜合
参考文献
  1. Jou, M.J.,Lin, J. J.(2009).Trees with the second largest number of maximal independent sets.Discrete Math.,309,4469-4474.
    連結：
  2. Chang, G. J.,Jou, M.J.(1999).The number of maximal independent sets in connected triangle-free graphs.Discrete Math.,197/198,169-178.
  3. Füredi, Z.(1987).The number of maximal independent sets in connected graphs.J. Graph Theory,11,463-470.
  4. Hujter, M.,Tuza, Z.(1993).The number of maximal indepdependent sets in triangle-free graphs.SIAM J. Discrete Math.,6,284-288.
  5. Jin, Z.,Yan, H.F.(2009).Trees with the second and third largest number of maximal independent sets.Ars Combin.,93,341-351.
  6. Jou, M.J.(1991).Taiwan,Department of Mathematics, National Central University.
  7. Jou, M.J.,Chang, G.J.(1995).Survey on conuntiny maximal independent sets.Proceedings of the Second Asian Mathematical Conference,Singapore:
  8. Jou, M.J.,Chang, G.J.,Lin, C.,Ma, T.H.(1996).A finiteness theorem for maximal independent sets.Graphs and Combin.,12,321-326.
  9. Lin, J. J.(2010).Quasi-tree graphs with the largest number of maximal independent sets.Ars Combin.,97,27-32.
  10. Lin, J. J.(2013).Quasi-tree graphs with the second largest number of maximal independent sets.Ars Combin.,108,257-267.
  11. Liu, H.,Lu, M.(2008).On the spectral radius of quasi-tree graphs.Linear Algebra Appl.,428,2708-2714.
  12. Liu, J.(1993).Maximal independent sets in bipartite graphs.J. Graph Theory,17,495-507.
  13. Moon, J. W.,Moser, J.(1965).On cliques in graphs.Israel J. Math.,3,23-28.
  14. Wilf, H. S.(1986).The number of maximal independent sets in a tree.SIAM J. Algebraic Discrete Methods,7,125-130.
print cancel