Independence number of graphs and line graphs of trees by means of omega invariant (Q2174305)

Let \(G\) be a graph of order \(n\) and size \(m\). Let \(\Delta\) denote the maximum degree among the vertices of \(G\), and let \(a_i\) denote the number of vertices of degree \(i\) in \(G\). It is well known that, for any tree \(T\), the following equality holds: \(a_1=2+\sum_{i=3}^{\Delta}(i-2)a_i\), i.e., \(\sum_{i=1}^{\Delta}(i-2)a_i=-2\). Let \(\Omega(G)=\sum_{i=1}^{\Delta}(i-2)a_i\). Then \(\Omega(G)=2(m-n)\) by the handshaking lemma. The authors examine the relation between \(\Omega(G)\) and some known graph parameters. They also examine an algorithmic aspect of independence number for trees and the line graph of trees.