论文摘要
研究图在点度数限制下的导出子图的大小是一个非常有趣的图论问题。Berman等人在树上得到了一系列优美的结果,并进一步提出了如下问题:对于树T,考察其最大顶点点集S(?)V(T),使得导出子图T[S]中所有点的度数要么为1,要么为0(mod k)。本文证明了对于正整数k≥2,任意树T都包含了大小至少为Ck|V(T)|的导出子图,使得导出子图所有点度数要么为1,要么为0(mod k),其中当k=2时ck=3/4;当k≥3时ck=2/3。这个界是紧的。从而解决了Berman提出的问题。
论文目录
文章来源
类型: 硕士论文
作者: 黄子扬
导师: 侯新民
关键词: 导出子图,点的度数,叶点
来源: 中国科学技术大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 中国科学技术大学
分类号: O157.5
总页数: 34
文件大小: 1565K
下载量: 9
相关论文文献
- [1].单图中的近似频繁子图挖掘算法[J]. 华东师范大学学报(自然科学版) 2019(06)
- [2].《吉祥多子图》临摹[J]. 大众文艺 2018(10)
- [3].吉祥多子图页[J]. 中国书画 2018(09)
- [4].在复杂网络中查找k个有限重叠的密集子图[J]. 计算机应用与软件 2016(12)
- [5].吉祥多子图[J]. 文艺研究 2017(03)
- [6].吉祥多子图[J]. 美与时代(中) 2017(06)
- [7].《吉祥多子图》[J]. 老年教育(书画艺术) 2016(01)
- [8].《吉祥多子图》[J]. 明日风尚 2016(08)
- [9].《吉祥多子图》[J]. 参花(上) 2016(06)
- [10].最大公共子图的约束符号求解方法[J]. 广西科学院学报 2017(01)
- [11].基于改进完全子图模型的关注对象多社区发现研究[J]. 南京理工大学学报 2016(06)
- [12].一种基于特征子图的不确定图分类算法[J]. 陕西师范大学学报(自然科学版) 2014(05)
- [13].指令扩展中相关子图的分析与处理[J]. 计算机辅助设计与图形学学报 2009(10)
- [14].因子图发展及其在定位与导航的应用技术[J]. 全球定位系统 2020(01)
- [15].具有最多与最少连通子图的单圈图[J]. 宜春学院学报 2015(03)
- [16].单圈图的连通子图的数目[J]. 南开大学学报(自然科学版) 2011(03)
- [17].改进的最大频繁子图挖掘算法[J]. 信息与电脑(理论版) 2017(18)
- [18].从不确定图中发现K紧密子图[J]. 计算机科学与探索 2011(09)
- [19].频繁子图挖掘研究综述[J]. 微电子学与计算机 2009(03)
- [20].频繁子图挖掘算法的应用分类[J]. 电脑知识与技术 2020(29)
- [21].加权最大频繁子图挖掘算法的研究[J]. 计算机工程与应用 2009(20)
- [22].一种挖掘最大频繁子图的新算法[J]. 系统仿真学报 2008(18)
- [23].基于子图模式的反恐情报关联图集分析[J]. 现代情报 2019(07)
- [24].具有结果多样性的近似子图查询算法[J]. 南京大学学报(自然科学) 2019(06)
- [25].频繁子图挖掘算法的若干问题[J]. 采矿技术 2011(05)
- [26].基于近似子图的规则空间压缩算法[J]. 自动化学报 2019(08)
- [27].一个复杂网络中完全子图的搜索算法[J]. 数学理论与应用 2013(03)
- [28].标签零模型及子图分布算法应用研究[J]. 小型微型计算机系统 2018(05)
- [29].特殊子图的计数[J]. 淮南职业技术学院学报 2011(03)
- [30].基于包含度的子图匹配方法[J]. 软件学报 2018(06)