On the differential in graphs Articles uri icon

publication date

  • July 2015

start page

  • 257

end page

  • 270

volume

  • 97

International Standard Serial Number (ISSN)

  • 0315-3681

abstract

  • Let Gamma(V, E) be a graph of order n, and let B(S) be the set of vertices in V \ S that have a neighbor in the set S. The differential of a set S is defined as partial derivative(5) = vertical bar B(S)vertical bar - vertical bar S vertical bar, and the differential of a graph to equal the max{partial derivative(S)} for any subset S of V. In this paper we obtain several tight bounds for the differential of a graph. In particular we investigate the relationship between the differential of a graph and the order, the minimum and maximum degree, and the diameter of the graph.