Maximum genus and maximum nonseparating independent set of a 3-regular graph
Maximum genus and maximum nonseparating independent set of a 3-regular graph
复制标题
DOI：
10.1016/s0012-365x(96)00299-3
复制
发表时间：
1997-11
期刊：
影响因子：
--
通讯作者：
Yuangqiu Huang;Yanpei Liu
中科院分区：
文献类型：
--
作者：
Yuangqiu Huang;Yanpei Liu
如果 J 是 G 的独立集，即 E ∩ {uv | ，则集合 J ⊆ V 称为连通图 G = (V, E) 的非分离独立集 (nsis)。 ∀u, v ∈ J} = 0，且 G − J 连通。我们称 z(G) = maxJ{|J||J 是 G 的 nsis} G 的 nsis 数。设 G 是一个 3-正则连通图；我们证明 G 的最大亏格，用 γM(G) 表示，等于 z(G)。然后，根据这个结果，得到了最大亏格γM(G)的一些新的表征。
A set J ⊆ V is called a nonseparating independent set (nsis) of a connected graph G = (V, E), if J is an independent set of G, i.e., E ∩ {uv | ∀u, v ∈ J} = 0, and G − J is connected. We call z(G) = maxJ{|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 γM(G), of G is equal to z(G). Then, according to this result, some new characterizations of the maximum genus γM(G) are obtained.