Nonseparating Independent Sets and Maximum Genus of Graphs

摘要

A subset I of vertices of an undirected connected graph G is a nonseparating independent set (NSIS) if no two vertices of I are adjacent and G - I is connected. Let Z(G) denote the cardinality of a maximum NSIS of G. A nonseparating independent set containing Z(G) vertices is called the maximum nonseparating independent set. In this paper, we firstly give an upper bound for Z(G) of regular graphs and determine Z(G) for some types of circular graphs. Secondly, we show a relationship between Z(G) and the maximum genus gamma(M)(G) of a general graph. Finally, an important formula is provided to compute Z(G), i.e., @@@ Z(G) = Sigma(x subset of I) d(I)(x) + 2(gamma(M)(G - I) - gamma(M)(G)) + (xi(G - I) - xi(G)), @@@ where I is the maximum nonseparating independent set and xi(G) is the Betti deficiency (Xuong, 1979) of G.

关键词