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}.