清晨好,您是今天最早来到科研通的研友!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您科研之路漫漫前行!

Triangulations Admit Dominating Sets of Size 2n/7.

组合数学 数学
作者
Aleksander B. G. Christiansen,Eva Rotenberg,Daniel Rutschmann
出处
期刊:Society for Industrial and Applied Mathematics eBooks [Society for Industrial and Applied Mathematics]
卷期号:: 1194-1240 被引量:2
标识
DOI:10.1137/1.9781611977912.47
摘要

We show that every planar triangulation on n > 10 vertices has a dominating set of size 2n/7 = n/3.5. This approaches the n/4 bound conjectured by Matheson and Tarjan [12], and improves significantly on the previous best bound of 17n/53 ≈ n/3.117 by Špacapan [18]. From our proof it follows that every 3-connected n-vertex near-triangulation (except for 3 sporadic examples) has a dominating set of size n/3.5. On the other hand, for 3-connected near-triangulations, we show a lower bound of 3(n−1)/11 ≈ n/3.666, demonstrating that the conjecture by Matheson and Tarjan [12] cannot be strengthened to 3-connected near-triangulations. Our proof uses a penalty function that, aside from the number of vertices, penalises vertices of degree 2 and specific constellations of neighbours of degree 3 along the boundary of the outer face. To facilitate induction, we not only consider near-triangulations, but a wider class of graphs (skeletal triangulations), allowing us to delete vertices more freely. Our main technical contribution is a set of attachments, that are small graphs we inductively attach to our graph, in order both to remember whether existing vertices are already dominated, and that serve as a tool in a divide and conquer approach. Along with a well-chosen potential function, we thus both remove and add vertices during the induction proof. We complement our proof with a constructive algorithm that returns a dominating set of size ≤ 2n/7. Our algorithm has a quadratic running time.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
6秒前
漂亮的半兰完成签到,获得积分10
9秒前
平常的丹秋完成签到,获得积分10
15秒前
jfw完成签到 ,获得积分10
16秒前
所所的应助被机灵的妙菡采纳,获得10
26秒前
在水一方的应助被机灵的妙菡采纳,获得30
27秒前
小马甲的应助被机灵的妙菡采纳,获得10
28秒前
29秒前
丘比特的应助被机灵的妙菡采纳,获得10
30秒前
可靠的夕阳完成签到,获得积分10
31秒前
CipherSage的应助被机灵的妙菡采纳,获得10
31秒前
Lucas的应助被机灵的妙菡采纳,获得10
32秒前
领导范儿的应助被机灵的妙菡采纳,获得20
33秒前
34秒前
鱼鱼完成签到 ,获得积分10
35秒前
小马甲的应助被机灵的妙菡采纳,获得10
35秒前
楚科研完成签到 ,获得积分10
35秒前
搜集达人的应助被机灵的妙菡采纳,获得10
36秒前
打打的应助被机灵的妙菡采纳,获得10
37秒前
852的应助被机灵的妙菡采纳,获得10
38秒前
思源的应助被机灵的妙菡采纳,获得30
39秒前
43秒前
开放的蚂蚁完成签到,获得积分10
56秒前
57秒前
1分钟前
1分钟前
受伤青丝完成签到,获得积分10
1分钟前
1分钟前
清爽笙完成签到,获得积分10
1分钟前
1分钟前
傲娇断天完成签到,获得积分10
1分钟前
1分钟前
369ninja发布了新的文献求助10
1分钟前
1分钟前
曾经的冰安完成签到,获得积分10
2分钟前
2分钟前
linyingo发布了新的文献求助10
2分钟前
2分钟前
369ninja发布了新的文献求助10
2分钟前
清爽水之完成签到,获得积分10
2分钟前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
Social Psychology in the Real World 600
八旗制度の研究 600
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8179961
求助须知:如何正确求助?哪些是违规求助? 9570183
关于积分的说明 21808480
捐赠科研通 7775861
什么是DOI,文献DOI怎么找? 3433251
关于科研通互助平台的介绍 2557383
邀请新用户注册赠送积分活动 2478978