کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418189 | 681617 | 2015 | 12 صفحه PDF | دانلود رایگان |
A potential function fGfG of a finite, simple and undirected graph G=(V,E)G=(V,E) is an arbitrary function fG:V(G)→N0fG:V(G)→N0 that assigns a nonnegative integer to every vertex of a graph GG. In this paper we define the iterative process of computing the step potential function qGqG such that qG(v)≤dG(v)qG(v)≤dG(v) for all v∈V(G)v∈V(G). We use this function in the development of new Caro–Wei-type and Brooks-type bounds for the independence number α(G)α(G) and the Grundy number Γ(G)Γ(G). In particular, we prove that Γ(G)≤Q(G)+1Γ(G)≤Q(G)+1, where Q(G)=max{qG(v)|v∈V(G)} and α(G)≥∑v∈V(G)(qG(v)+1)−1α(G)≥∑v∈V(G)(qG(v)+1)−1. This also establishes new bounds for the number of colors used by the algorithm Greedy and the size of an independent set generated by a suitably modified version of the classical algorithm GreedyMAX.
Journal: Discrete Applied Mathematics - Volume 182, 19 February 2015, Pages 61–72