图的独立数的一个新下界

A NEW LOWER BOUND ON THE INDEPENDENCE NUMBER OF A GRAPH

设α（Ｇ）表示简单图Ｇ＝（Ｖ，Ｅ）的独立数．本文给出了α（Ｇ）的一个新的下界：α（Ｇ）≥∑ｖ∈Ｖ（λｄ（ｖ）＋１）／（ｄ（ｖ）＋λｄ（ｖ）＋１），其中λｄ（ｖ）＝ｍａｘ｛０，βＮ（ｖ）－ｄ（ｖ）｝，ｄ（ｖ）＝｜Ｎ（ｖ）｜，Ｎ（ｖ）＝｛ｗ∈Ｖ｜（ｖ，ｗ）∈Ｅ｝，βＮ（ｖ）＝ｍｉｎｗ∈Ｎ（ｖ）ｄ（ｗ）．

Let α(G) denote the independence number of a simple graph, G=(V,E). In this paper, a new lower bound on α(G) is established: α(G)≥∑v∈V(λ d(v) +1)/(d(v)+λ d(v) +1), where λ d(v) = max {0,β N(v) -d(v)},d(v)=|N(v)|,N(v)={w∈V|(v,w)∈E},β N(v) = min w∈N(v)d(w).