2-连接图中X-最长圈下界新估计:2000年进展
需积分: 9 171 浏览量
更新于2024-08-12
收藏 519KB PDF 举报
本文档标题为《2-连通图中X-最长圈下界估计》(2000年),发表在《云南民族大学(自然科学版)》期刊上。作者 Luo Hong 和 Cai Guangcheng 对于给定的图G,其中X是图中的一个顶点集合,他们提出了新的参数来分析2-连通图中的特定循环结构。这些参数包括IX(X),表示G[X](X诱导子图中最大独立集的大小),ak(X)(最小的顶点独立集权重之和),以及NCk(X)(最小的k元独立集集合的大小,k>2)。
文章的核心内容是改进了对于一个2-连通图G,当其阶数n满足n>3,且有特定条件X的3-度数3(X)小于等于n+r-2时,关于X-最长圈(X-longest cycle)下界的估计。这里所谓的X-最长圈指的是包含顶点X且长度尽可能大的独立闭合路径。研究者证明,这样的图G中存在一个至少包含min{IX(X), IX(X)+NCr+2+e(n+r)(X)-a(X)}个X的顶点的圈,其中e(n+r)(X)是X的(n+r)邻域中的边数,a(X)是X的最大独立集的大小。
文中还引入了X-dominating cycle的概念,即覆盖X的顶点集的最小圈,这在确定图的结构和复杂性方面具有重要意义。2-连通图的讨论是基于Bondy和Murty[2]的工作,但只考虑简单图。本文的结果对于理解复杂网络中关键顶点集的连接性和路径特性具有理论价值,同时也为实际应用中寻找有效算法和优化策略提供了数学依据。
关键词:X-最长圈、X-dominating cycle、2-连通图
分类号:0144.5
文献标识符:Article ID: 1005-7188(2000)01-∞09-04
文章主要探讨了以下几点:
1. 定义和参数的计算方法。
2. 下界估计的推导过程和证明。
3. 结果的应用场景,如网络设计、图论分析等。
4. 与已知理论的关联,如Bondy-Murty的工作。
总结来说,这篇文章深入探讨了2-连通图中特定结构与图的下界估计之间的关系,对于理解和优化这类图的性质有着重要的学术价值。
2019-09-20 上传
2024-06-14 上传
2023-05-21 上传
2024-04-24 上传
2023-05-15 上传
2023-11-18 上传
2023-05-18 上传
2023-06-03 上传
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
weixin_38745925
- 粉丝: 28
- 资源: 890
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命