On local and global independence numbers of a graph
The local independence number ?i(G) of a graph G at a distance i is the maximum number of independent vertices at distance i from any vertex. We study the impact of restricting ?i(G) on the (global) independence number ?(G). Among others, we show that in graphs with bounded diameter, ?(G) is bounded if and only if ?i(G) is bounded for at least one i, 2?i?(diam(G)?1)/4.
05c69