A sharp upper bound for the number of stable sets in graphs with given number of cut edges

Let G be a connected and simple graph, and let i ( G ) denote the number of stable sets in G . In this letter, we have presented a sharp upper bound for the i ( G ) -value among the set of graphs with k cut edges for all possible values of k , and characterized the corresponding extremal graphs as w...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics letters 2009-09, Vol.22 (9), p.1380-1385
Main Author: Hua, Hongbo
Format: Article
Language:English
Subjects:
2-edge-connected graph
Cut edge
Exact sciences and technology
Extremal graph
Mathematical analysis
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Sciences and techniques of general use
Stable set
Upper bound
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a connected and simple graph, and let i ( G ) denote the number of stable sets in G . In this letter, we have presented a sharp upper bound for the i ( G ) -value among the set of graphs with k cut edges for all possible values of k , and characterized the corresponding extremal graphs as well.
ISSN:0893-9659
1873-5452
DOI:10.1016/j.aml.2009.03.011