Fibonacci numbers and Lucas numbers in graphs

被引：14

作者：

Startek, Mariusz ^{[1
]}

Wloch, Andrzej ^{[1
]}

Wloch, Iwona ^{[1
]}

机构：

[1] Rzeszow Tech Univ, Fac Math & Appl Phys, PL-35959 Rzeszow, Poland

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 04期

关键词：

Independent sets; Fibonacci numbers; Counting; INDEPENDENT SETS; TREES;

D O I：

10.1016/j.dam.2008.08.028

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A subset S C V(G) is independent if no two vertices of S are adjacent in G. In this paper we study the number of independent sets in graphs with two elementary cycles. In particular we determine the smallest number and the largest number of these sets among n-vertex graphs with two elementary cycles. The extremal values of the number of independent sets are described using Fibonacci numbers and Lucas numbers. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：864 / 868

页数：5

共 12 条

[1] [Anonymous], 2005, GRAPH THEORY
[2] GUTMAN I, 1986, TOPOLOGICAL CONCEPTS
[3] Lin C., 1995, CHIN J MATH, V23, P199
[4] Merrifield R. E., 1989, Topological Methods in Chemistry
[5] Bounds on the number of vertex independent sets in a graph
Pedersen, Anders Sune
Vestergaard, Preben Dahl
[J]. TAIWANESE JOURNAL OF MATHEMATICS, 2006, 10 (06): : 1575 - 1587
[6] The number of independent sets in unicyclic graphs
Pedersen, AS
Vestergaard, PD
[J]. DISCRETE APPLIED MATHEMATICS, 2005, 152 (1-3) : 246 - 256
[7] PRODINGER H, 1982, FIBONACCI QUART, V20, P16
[8] TRINAJSTIC N, 1982, CHEM GRAPH THEORY
[9] Wagner SG, 2007, MATCH-COMMUN MATH CO, V57, P221
[10] Trees with extremal numbers of maximal independent sets including the set of leaves
Wloch, Iwona
[J]. DISCRETE MATHEMATICS, 2008, 308 (20) : 4768 - 4772

← 1 2 →