Dominating sets in triangulations on surfaces
Dominating sets in triangulations on surfaces
复制标题
DOI：
10.26493/1855-3974.200.fbe
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
Hong Liu;M. Pelsmajer
中科院分区：
文献类型：
--
作者：
Hong Liu;M. Pelsmajer
图G的一个控制集D ∈ V（G）是这样的一个集合，使得每个顶点v ∈ V（G）要么在该集合中，要么与该集合中的一个顶点相邻。Matheson和Tarjan（1996）证明了任意n -顶点平面三角剖分都有一个大小不超过n /3的控制集，并且当n足够大时，给出了n /4的界。King和Pelsmajer最近证明了这一点，最大度至多为6。Plummer和Za（2009）以及Honjo、Kawarabayashi和Nakamoto（2009）将n /3界扩展到曲面上的三角剖分。我们证明了两个相关的结果：（i）存在一个常数c1，使得任何最大度至多为6的n -顶点平面三角剖分都有一个大小至多为n /6 + c1的控制集。(ii)对任意曲面S，t ≥ 0，e > 0，存在c2使得对S上任意n -顶点三角剖分且至多t个顶点的度不等于6，存在大小至多为n（1/6 + e）+c2的控制集。作为证明的一部分，我们还证明了不可定向曲面的任何n -顶点三角剖分都有一个长度不超过2 <$n的不可收缩圈。Albertson和哈钦森（1986）证明了对于非球面的可定向曲面的n -顶点三角剖分有一个长度为n（2 n）的不可收缩圈，但对于不可定向曲面还没有类似的结果。
A dominating set D ⊆ V ( G ) of a graph G is a set such that each vertex v ∈ V ( G ) is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any n -vertex plane triangulation has a dominating set of size at most n /3, and conjectured a bound of n /4 for n sufficiently large. King and Pelsmajer recently proved this for graphs with maximum degree at most 6. Plummer and Zha (2009) and Honjo, Kawarabayashi, and Nakamoto (2009) extended the n /3 bound to triangulations on surfaces. We prove two related results: (i) There is a constant c 1 such that any n -vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most n /6 + c 1 . (ii) For any surface S , t ≥ 0, and e > 0, there exists c 2 such that for any n -vertex triangulation on S with at most t vertices of degree other than 6, there is a dominating set of size at most n (1/6 + e ) + c 2 . As part of the proof, we also show that any n -vertex triangulation of a non-orientable surface has a non-contractible cycle of length at most 2√ n . Albertson and Hutchinson (1986) proved that for n -vertex triangulation of an orientable surface other than a sphere has a non-contractible cycle of length √(2 n ), but no similar result was known for non-orientable surfaces.