Nonseparating Independent Sets and Maximum Genus of Graphs

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

作者机构：Center of Intelligent Computing and Applied StatisticsSchool of MathematicsPhysics and StatisticsShanghai University of Engineering ScienceShanghai 201620China School of Mathematical SciencesEast China Normal UniversityShanghai 200241China Shanghai Key Laboratory of PMMPShanghai 200241China School of MathematicsRenmin University of ChinaBeijing 100872China 

出 版 物：《Acta Mathematicae Applicatae Sinica》 (应用数学学报（英文版）)

年 卷 期：2022年第38卷第3期

页      面：719-728页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by the National Natural Science Foundation of China(Nos.11171114,11401576,61662066,62072296) Science and Technology Commission of Shanghai Municipality(No.13dz2260400)。 

主　　题：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 M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.