If is a simple connected graph with the vertex set and the edge set , S is a subset of , and let be the set of neighbors of S in . Then, the differential of S is defined as . The differential of G, denoted by , is the maximum value of for all subsets . The graph operator is defined as the graph that results by subdividing every edge of G once and joining pairs of these new vertices iff their corresponding edges are incident in G. In this paper, we study the relations between and . Besides, we exhibit some results relating the differential and well-known graph invariants, such as the domination number, the independence number, and the vertex-cover number.
Let be a simple graph with vertex set V and edge set E. Let D be a subset of V, and let be the set of neighbours of D in . The differential of D is defined as . The maximum value of taken over all subsets is the differential of G. For , the β-differential of G is the maximum value of . Motivated by an influential maximization problem, in this paper we study the -differential of G.
14 December 2018 in Acta Mathematica Sinica, English Series
Let be a graph, and let . Motivated by a service coverage maximization problem with limited resources, we study the -differential of G. The β-differential of G, denoted by , is defined as . The case in which is known as the differential of G, and hence can be considered as a generalization of the differential of G. In this paper, upper and lower bounds for are given in terms of its order , minimum degree , maximum degree , among other invariants of G. Likewise, the -differential for graphs with heavy vertices is studied, extending the set of applications that this concept can have.