Neighborhood unions and regularity in graphs

One way to generalize the concept of degree in a graph is to consider the neighborhood N(S) of an independent set S instead of a simple vertex. The minimum generalized degree of order t of G is then defined, for I less than or equal to t less than or equal to alpha (the independence number of G), by u(t) = min {\N(S)\: S subset of V, S is independent and \S \ = t}. The graph G is said to be u(t)-regular if \N(S-t)\ = \N(S-2)\ for every pair S-1,S-2 of independent sets of t elements, totally u(t)-regular (resp. totally u(t less than or equal tos)-regular where s is given less than or equal to alpha) if it is u(t)-regular for every t less than or equal to alpha (resp. for every t less than or equal to s), strongly u(t)-regular (resp. strongly u(t less than or equal tos)-regular) if \N(S-1)\ = \N(S-2)\ for every pair S-1,S-2 of independent sets of G (resp. every pair of independent sets of order at most s). We determine the strongly u(t less than or equal to2)-regular graphs and give some properties of the totally u(t less than or equal to2)-regular and totally u(t)-regular graphs. Some of our results improve already known results. (C) 2001 Elsevier Science B.V. All rights reserved.