题名

Alternative Proofs of Results on the Number of Independent Sets in Trees

并列篇名

樹圖中獨立集個數結果的另一種證明

作者

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

关键词

獨立集 ； 樹圖 ； 極圖 ； 斐波那契數 ； 三腳架圖 ； independent set ； tree ； extremal graph ； Fibonacci number ； tripod graph

期刊名称

嶺東學報

卷期/出版年月

37期（2015 / 06 / 01）

页次

207 - 216

内容语文

英文
中文摘要

圖形G＝（V,E）中獨立集為點集V之一子集合S，且使得S中任兩點在G中均不相連。在本篇論文中，我們以另一種較簡易方法得到樹圖中獨立集個數的最大、第二大、最小及第二小數值等已知的結果。除此之外，我們亦描繪出達到這些數值之所有極圖。
英文摘要

In a graph G=(V, E), an independent set is a subset S of V such that no two vertices in S are adjacent. In this paper, we will give alternative proofs for the solutions to readily determine the largest, second largest and the smallest, second smallest number of independent sets among all trees. Extremal graphs achieving these values are also given.
主题分类 人文學 > 人文學綜合
人文學 > 歷史學
基礎與應用科學 > 資訊科學
社會科學 > 社會科學綜合
参考文献
  1. Jou, M.-J.(1996).Taiwan,Department of Applied Mathematics, National Chiao Tung University.
  2. Jou, M.-J.(1991).Taiwan,Department of Mathematics, National Central University.
  3. Lin, S.-B.,Lin, C.(1995).Trees and forests with large and small independent indices.Chiness J. Math.,23,199-210.
  4. Prodinger, H.,Tichy, R.F.(1982).Fibonacci numbers of graphs.Fibonacci Quarterly,20,16-21.
print cancel