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 条
  • [21] A note on the number of matchings and independent sets in trees
    Fischermann, M
    Volkmann, L
    Rautenbach, D
    DISCRETE APPLIED MATHEMATICS, 2005, 145 (03) : 483 - 489
  • [22] Counting independent sets in Riordan graphs
    Cheon, Gi-Sang
    Jung, Ji-Hwan
    Kang, Bumtle
    Kim, Hana
    Kim, Suh-Ryung
    Kitaev, Sergey
    Mojallal, Seyed Ahmad
    DISCRETE MATHEMATICS, 2020, 343 (11)
  • [23] The number of maximal independent sets in connected triangle-free graphs
    Chang, GJ
    Jou, MJ
    DISCRETE MATHEMATICS, 1999, 197 (1-3) : 169 - 178
  • [24] On disjoint maximum and maximal independent sets in graphs and inverse independence number
    Kaci, Fatma
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (08)
  • [25] Enumerating independent vertex sets in grid graphs
    Oh, Seungsang
    Lee, Sangyop
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 510 : 192 - 204
  • [26] The average size of independent sets in unicyclic graphs
    Luo, Zuwen
    Xu, Kexiang
    Cevik, Ahmet Sinan
    Gutman, Ivan
    CONTRIBUTIONS TO MATHEMATICS, 2023, 7 : 1 - 10
  • [27] Augmenting graphs for independent sets
    Alekseev, VE
    Lozin, VV
    DISCRETE APPLIED MATHEMATICS, 2004, 145 (01) : 3 - 10
  • [28] A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
    Kurita, Kazuhiro
    Wasa, Kunihiro
    Uno, Takeaki
    Arimura, Hiroki
    THEORETICAL COMPUTER SCIENCE, 2021, 874 : 32 - 41
  • [29] Maximizing the number of independent sets of fixed size in K n-covered graphs
    Wang, Anyao
    Hou, Xinmin
    Liu, Boyuan
    Ma, Yue
    JOURNAL OF GRAPH THEORY, 2022, 99 (02) : 175 - 185
  • [30] Counting independent sets in cocomparability graphs
    Dyer, Martin
    Mueller, Haiko
    INFORMATION PROCESSING LETTERS, 2019, 144 : 31 - 36
12345