The differential on graph operator R(G)

¹ Facultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame No.54 Col. Garita, 39650 Acalpulco Gro., Mexico
² Academic Unit of Mathematics, Autonomous University of Zacatecas. Paseo la Bufa, int. Calzada Solidaridad, 98060 Zacatecas, Mexico

^* Corresponding author: orosario@uagro.mx

Received: 22 April 2024
Accepted: 2 November 2024

Abstract

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.