DIFFERENTIALS IN CERTAIN CLASSES OF GRAPHS

Abstract. Let X ⊂ V be a set of vertices in a graph G = (V, E). The boundary B(X) of X is defined to be the set of vertices in V − X dominated by vertices in X, that is, B(X) = (V − X) ∩ N(X). The differential ∂(X) of X equals the value ∂(X) = |B(X) | − |X|. The differential of a graph G is defined as ∂(G) = max{∂(X)|X ⊂ V}. It is easy to see that for any graph G having vertices of maximum degree ∆(G), ∂(G) ≥ ∆(G)−1. In this paper we characterize the classes of unicyclic graphs, split graphs, grid graphs, k-regular graphs, for k ≤ 4, and bipartite graphs for which ∂(G) = ∆(G) − 1. We also determine the value of ∂(T) for any complete binary tree T. 1