Graphs with Maximum and Minimum Independence Numbers


Ivan Gutman


If $r(G,k)$ is the number of selections of $k$ independent vertices in a graph $G$, and if $r(G,k)>r(H, k)$, the graph $G$ is $i$-greater than the graph $H$. The maximal and the minimal graphs w.r.t. the above property are determined in the class of acyclic, unicyclic, connected acyclic and connected unicyclic graphs.