The k-independence number of t-connected graphs

摘要

A set S⊆V(G) is a k-independent set of a graph G if the distance between every two vertices of S is greater than k. The k-independence number αk(G) of G is the maximum cardinality over all k-independent set in G. In this note, we show that if G is a t-connected graph of order n, then α2k+1(G)≤max{1,n−ttk+1} and α2k(G)≤max{1,ntk+1} for any integer k≥0. Both bounds are sharp. For any integer s≥2,p(G,s)=max{min1≤i≤j≤sd(vi,vj):{v1,…,vs}⊆V(G)},is a generalization of the diameter of G. We determine the exact value of the maximum p(G,s) among all t-connected graphs of order n. This includes the main results of a recent paper by Knor and Škrekovski (On the minimum distance in a k-vertex set in a graph, Appl. Math. Comput. 356 (2019) 99–104) and solve an open problem therein.