On the k-distance differential of graphs

Abstract

Let G = (V, E) be a graph and X ? V . The differential of X is defined as ?(X) = |B(X)| ? |X| where B(X) is a set of all vertices in V ? X which has adjacent vertex in the set X. Also, the differential of a graph G written ?(G), is equal to max{?(X) : X ? V }. In this paper, we initiate the study of k-distance differential of graphs which is a generalization of differential of graphs. In addition, we show that for any connected graph G of order n ? k + 2, the number (2k?1)n / 2k+3 is a sharp lower bound for k-distance differential of G. We also obtain upper bounds for k-distance differential of graphs. Finally, we characterize the graphs whose k-distance differential belongs to {n ? 2, n ? 3, 1}.