Axioms (Oct 2021)

General Properties on Differential Sets of a Graph

  • Ludwin A. Basilio,
  • Sergio Bermudo,
  • Juan C. Hernández-Gómez,
  • José M. Sigarreta

DOI
https://doi.org/10.3390/axioms10040265
Journal volume & issue
Vol. 10, no. 4
p. 265

Abstract

Read online

Let G=(V,E) be a graph, and let β∈R. Motivated by a service coverage maximization problem with limited resources, we study the β-differential of G. The β-differential of G, denoted by ∂β(G), is defined as ∂β(G):=max{|B(S)|−β|S|suchthatS⊆V}. The case in which β=1 is known as the differential of G, and hence ∂β(G) can be considered as a generalization of the differential ∂(G) of G. In this paper, upper and lower bounds for ∂β(G) are given in terms of its order |G|, minimum degree δ(G), maximum degree Δ(G), 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.

Keywords