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 条
  • [1] The number of independent sets of tricyclic graphs
    Zhu, Zhongxun
    Yu, Qigang
    APPLIED MATHEMATICS LETTERS, 2012, 25 (10) : 1327 - 1334
  • [2] Counting independent sets in tricyclic graphs
    Poureidi, Abolfazl
    DISCRETE APPLIED MATHEMATICS, 2023, 331 : 138 - 146
  • [3] The number of independent sets of unicyclic graphs with given matching number
    Chen, Gong
    Zhu, Zhongxun
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (1-2) : 108 - 115
  • [4] The Number of Independent Sets In Hexagonal Graphs
    Deng, Zhun
    Ding, Jie
    Heal, Kathryn
    Tarokh, Vahid
    2017 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2017, : 2910 - 2914
  • [5] ON THE NUMBER OF MAXIMUM INDEPENDENT SETS OF GRAPHS
    Derikvand, T.
    Oboudi, M. R.
    TRANSACTIONS ON COMBINATORICS, 2014, 3 (01) : 29 - 36
  • [6] The number of maximum independent sets in graphs
    Jou, MJ
    Chang, GJ
    TAIWANESE JOURNAL OF MATHEMATICS, 2000, 4 (04): : 685 - 695
  • [7] Counting the number of independent sets in chordal graphs
    Okamoto, Yoshio
    Uno, Takeaki
    Uehara, Ryuhei
    JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (02) : 229 - 242
  • [8] On the Number of -Dominating Independent Sets in Planar Graphs
    Taletskii D.S.
    Journal of Applied and Industrial Mathematics, 2024, 18 (01) : 167 - 178
  • [9] ON THE NUMBER OF MAXIMUM INDEPENDENT SETS IN DOOB GRAPHS
    Krotov, D. S.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2015, 12 : 508 - 512
  • [10] The number of independent sets in bipartite graphs and benzenoids
    Han, Michael
    Herlihy, Sycamore
    Kuenzel, Kirsti
    Martin, Daniel
    Schmidt, Rachel
    AEQUATIONES MATHEMATICAE, 2024, : 1175 - 1195
12345