Independence and average distance in graphs (Q1363759): Difference between revisions

Let \(G=(V,E)\) be a simple connected graph of order \(n\geq 2\) and let \(k\) be a positive integer. A subset \(X\) of \(V\) is \(k\)-independent if the distance between every two vertices of \(X\) is at least \(k+1\). The \(k\)-independence number of \(G\), \(I_k(G)\), is defined to be the maximum cardinality over all \(k\)-independent sets of \(G\). The average distance of \(G\) is \(\mu(G)=\sum_{x,y\in V} d(x,y)/{n\choose 2}\). A sharp upper bound for \(I_k(G)\) is obtained in terms of \(k\) and \(n\). Furthermore, a lower bound, also sharp, is derived for \(\mu(G)\) in relation to \(k\), \(n\), and \(I_k(G)\), thus generalizing results of \textit{F. R. K. Chung} [J. Graph Theory 12, No. 2, 229-235 (1988; Zbl 0644.05029] and \textit{P. Dankelman} [Discrete Appl. Math. 51, No. 1-2, 75-83 (1994; Zbl 0803.05020)].