| Summary: | Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> be a graph, and let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>β</mi><mo>∈</mo><mi mathvariant="double-struck">R</mi></mrow></semantics></math></inline-formula>. Motivated by a service coverage maximization problem with limited resources, we study the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>β</mi></semantics></math></inline-formula>-differential of <i>G</i>. The <i>β-differential</i> of <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∂</mo><mi>β</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, is defined as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∂</mo><mi>β</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>:</mo><mo>=</mo><mo movablelimits="true" form="prefix">max</mo><mrow><mo>{</mo><mo>|</mo><mi>B</mi><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow><mo>|</mo><mo>−</mo><mi>β</mi><mo>|</mo><mi>S</mi><mo>|</mo><mspace width="0.166667em"></mspace><mspace width="0.166667em"></mspace><mrow><mi>s</mi><mi>u</mi><mi>c</mi><mi>h</mi><mi>t</mi><mi>h</mi><mi>a</mi><mi>t</mi></mrow><mspace width="0.166667em"></mspace><mspace width="0.166667em"></mspace><mi>S</mi><mo>⊆</mo><mi>V</mi><mo>}</mo></mrow></mrow></semantics></math></inline-formula>. The case in which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>β</mi><mo>=</mo><mn>1</mn></mrow></semantics></math></inline-formula> is known as the <i>differential</i> of <i>G</i>, and hence <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∂</mo><mi>β</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> can be considered as a generalization of the differential <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>∂</mo><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of <i>G</i>. In this paper, upper and lower bounds for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>∂</mo><mi>β</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> are given in terms of its order <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>|</mo><mi>G</mi><mo>|</mo></mrow></semantics></math></inline-formula>, minimum degree <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>δ</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, maximum degree <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>Δ</mo><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, among other invariants of <i>G</i>. Likewise, the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>β</mi></semantics></math></inline-formula>-differential for graphs with heavy vertices is studied, extending the set of applications that this concept can have.
|
|---|