Nonseparating Independent Sets and Maximum Genus of Graphs

作者：YANG, Chao^*; REN, Han; WEI, Er-ling

来源：Acta Mathematicae Applicatae Sinica-English Series, 2022, 38(3): 719-728.

DOI：10.1007/s10255-022-1111-7

• nonseparating independent sets
• maximum genus
• graph embedding
• decycling set

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.