ON THE k-DISTANCE DIFFERENTIAL OF GRAPHS

ON THE k-DISTANCE DIFFERENTIAL OF GRAPHS

D. A. Mojdeh, I. Masoumi

[PDF]

Abstract

Let G = (V;E) be a graph and X   V . The di erential of X is de ned as @(X) = jB(X)j jXj where B(X) is a set of all vertices in V X which has adja- cent vertex in the set X. Also, the di erential of a graph G written @(G), is equal to maxf@(X) : X   V g. In this paper, we initiate the study of k-distance di erential of graphs which is a generalization of di erential of graphs. In addition, we show that for any connected graph G of order n   k + 2, the number (2k1)n 2k+3 is a sharp lower bound for k-distance di erential of G. We also obtain upper bounds for k-distance di erential of graphs. Finally, we characterize the graphs whose k-distance di erential belongs to fn 2; n 3; 1g.

Keywords

Di erential of graphs, k-distance domination, k-distance di erential of graph, domination number of graphs.