Search

Win proved a very famous conclusion that states the graph G with connectivity κ (G) , independence number α (G) and α (G) ≤ κ (G) + k − 1 (k ≥ 2) contains a spanning k-ended tree. This means that there exists a spanning tree with at most k leaves. In this paper, we strengthen the Win theorem to the following: Let G be a simple 2-connected graph such that | V (G) | ≥ 2 κ (G) + k , α (G) ≤ κ (G) + k (k ≥ 2) and the number of maximum independent sets of cardinality κ + k is at most n − 2 κ − k + 1 . Then, either G contains a spanning k-ended tree or a subgraph of K κ ∨ ((k + κ − 1) K 1 ∪ K n − 2 κ − k + 1) . [ABSTRACT FROM AUTHOR]

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 | s u c h t h a t S ⊆ 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. [ABSTRACT FROM AUTHOR]