On the number of dependent sets in a connected graph
|Title||On the number of dependent sets in a connected graph|
|Author(s)||D. G. C. Horrocks|
|Abstract||A set X of vertices of a graph is said to be dependent if X is not an independent set. For the graph G, let P-k(G) denote the set of dependent sets of cardinality k. In this paper, we show that if G is a connected graph on 2n vertices where n greater than or equal to 3 then \P-n(G)\ greater than or equal to \Pn+1(G)\. This study is motivated by a conjecture of Lih.|
Using APA 6th Edition citation style.
Times viewed: 285