BOUNDS ON THE NUMBER OF VERTEX INDEPENDENT SETS IN A GRAPH
Anders Sune Pedersen, Preben Dahl Vestergaard · University of Southern Denmark Research Portal (University of Southern Denmark) · 2006
Abstract. We consider the number of vertex independent sets i(G). In general, the problem of determining the value of i(G) is NP-complete. We present several upper and lower bounds for i(G) in terms of order, size or independence number. We obtain improved bounds for i(G) on restricted graph classes such as the bipartite graphs, unicyclic graphs, regular graphs and claw-free graphs. 1. NOTATION We denote by G a graph of order n = |V (G) | and size m = |E(G)|. For a vertex x in V (G) let deg G(x) denote its degree. Aleaf is a vertex of degree one and a stem is a vertex adjacent to a leaf. Pn denotes a path on n vertices and Cn a cycle on n vertices. The diameter of a graph G is the maximum distance between two vertices in G. The complement of G is denoted by G. The complete graph on n vertices is denoted by Kn, while Kn denotes the graph consisting of n isolated vertices. By K1,n−1 we denote the star consisting of one center vertex adjacent to n − 1 leaves. A corona graph G is a graph in which each vertex is a leaf or is a stem adjacent to exactly one leaf. If H is a graph, then H ◦ K1 denotes the corona graph constructed from H by attaching precisely one leaf at each vertex of H. A graph is called unicyclic if it is connected and contains exactly one cycle. The Fibonacci numbers, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,... are defined recursively by F (0) = 0,F(1) = 1, and for n ≥ 2, F (n) =F (n − 2) + F (n − 1). The Lucas numbers are L(n) =F (n − 1) + F (n +1)for n ≥ 1. Given a graph G, a subset S ⊆ V (G) is called independent if no two vertices of S are adjacent in G. The independence number of G, denoted by α(G), is the cardinality of a largest independent set S in G. The set of independent sets in G is denoted by I(G).