On the number of independent sets in cycle-separated tricyclic graphs

被引：3
|
作者：
Dolati, Ardeshir [1 ]
机构：
[1] Shahed Univ, Dept Math, Tehran, Iran
来源：
COMPUTERS & MATHEMATICS WITH APPLICATIONS | 2011年 / 61卷 / 06期
关键词：
Cycle-separated tricyclic graph; Independent set; Fibonacci number; Max-touch-vertex; Tight bound; MERRIFIELD-SIMMONS INDEX; HOSOYA INDEX;
D O I：
10.1016/j.camwa.2011.01.021
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A cycle-separated tricyclic graph (CSTC graph) is a connected simple graph with n vertices and n + 2 edges whose subgraph induced by its cycles consists of three disjoint cycles. In this paper we investigate the number of independent sets in CSTC graphs. We show that the tight upper bound for the number of independent sets in the n-vertex CSTC graphs is 48 x 2(n-9) + 9 (for n >= 9); we also characterize the extremal graph with respect to the aforementioned bound. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1542 / 1546
页数：5
相关论文
共 50 条
12345