题名

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

并列篇名

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

DOI

10.29850/LTJ.201106.0006

作者

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

关键词

獨立集 ； 孤立點 ； 林圖 ； 極圖 ； independent set ； isolated vertex ； forest ； extremal graph

期刊名称

嶺東學報

卷期/出版年月

29期（2011 / 06 / 01）

页次

127 - 132

内容语文

英文
中文摘要

圖形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.
主题分类 人文學 > 人文學綜合
人文學 > 歷史學
基礎與應用科學 > 資訊科學
社會科學 > 社會科學綜合
参考文献
  1. M.-J. Jou, Independent sets in trees, to appear in Ars Combinatoria..
  2. Jou, M.-J(1996).Taiwan,Department of Applied Mathematics of National Chiao Tung University.
  3. Knopfmacher, A.,Tichy, R. F.,Wagner, S.,Ziegler, V.(2007).Graphs, partitions and Fibonacci numbers.Discrete Appl. Math,155,1175-1187.
  4. Li, S.,Zhu, Z.(2009).The number of independent sets in unicyclic graphs with a given diameter.Discrete Appl. Math,157,1387-1395.
  5. Lin, S. B.,Lin, C.(1995).Trees and forests with large and small independent indices.Chinese J. Math,23,199-210.
  6. Pedersen, A. S.,Vestergaard, P. D.(2005).Vestergaard, The number of independent sets in unicyclic graphs.Discrete Appl. Math,152,246-256.
  7. Prodinger, H.,Tichy, R. F.(1982).Fibonacci numbers of graphs.Fibonacci Quart,20,16-21.
  8. Wagner, S. G.(2006).The Fibonacci number of generalized Petersen graphs.Fi-bonacci Quart,44,362-367.
print cancel