Maximum genus and maximum nonseparating independent set of a 3-regular graph

被引:13
作者
Huang, YQ
Liu, YP
机构
[1] NO JIAOTONG UNIV,DEPT MATH,BEIJING 100044,PEOPLES R CHINA
[2] HUNAN NORMAL UNIV,DEPT MATH,CHANGSHA 410081,PEOPLES R CHINA
关键词
D O I
10.1016/S0012-365X(96)00299-3
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A set J subset of or equal to V is called a nonseparating independent set (nsis) of a connected graph G = (V,E), ii. J is an independent set of G, i.e., E boolean AND {u upsilon/For All u, upsilon is an element of J} = 0, and G - J is connected. We call z(G) = max(j){\J\/J is an nsis of G} the nsis number of G. Let G be a 3-regular connected graph; we prove that the maximum genus, denoted by gamma(M)(G), of G is equal to z(G). Then, according to this result, some new characterizations of the maximum genus gamma(M)(G) are obtained.
引用
收藏
页码:149 / 158
页数:10
相关论文
共 12 条