The differential on graph operator R(<i>G</i>)

Let G = ( V ( G ), E ( G )) be a simple graph with vertex set V ( G ) and edge set E ( G ). Let S be a subset of V ( G ), and let B ( S ) be the set of neighbours of S in V ( G ) ∖S . The differential ∂ ( S ) of S is the number |B ( S ) |−|S| . The maximum value of ∂ ( S ) taken over all subsets S ⊆ V ( G ) is the differential ∂ ( G ) of G . The graph R( G ) is defined as the graph obtained from G by adding a new vertex v e for each e ∈ E ( G ), and by joining v e to the end vertices of e . In this paper we study the relationship between ∂ ( G ) and ∂ (R( G )), and give tight asymptotic bounds for ∂ (R( G )). We also exhibit some relationships between certain vertex sets of G and R( G ) which involve well known graph theoretical parameters.