项目名称: 带限制条件的凯莱图顶点划分研究

项目编号: No.11426085

项目类型: 专项基金项目

立项/批准年度: 2015

项目学科: 数理科学和化学

项目作者: 李锐

作者单位: 河海大学

项目金额: 3万元

中文摘要: 将图的顶点集或边集按特定要求划分成点子集或边子集的问题称为图的划分问题. 图的划分问题首先关注划分的存在性;其次,在这些划分上优化某些成本函数.凯莱图,由于构造简单以及高对称性,越来越受到图论学者的重视,已成为图论研究的一个重要领域. 凯莱图的结构特性,与网络稳定性相关的连通度,超连通性以及各类限制性连通度都得到了广泛研究. 本项目主要研究凯莱图的带连通度和最小度限制的划分问题.设k是任意正整数.我们希望找到一个线性函数f(k),使得任意f(k)-连通(或最小度为f(k))的凯莱图都存在划分 (S,T) 使得S和T所诱导的子图都是k-连通的(或最小度至少为k),且S中每个元素在T中都有k个邻点.

中文关键词: 划分;连通度;最小度;无三圈图;

英文摘要: Graph partitioning problems ask for a partition of the vertex or edge set of a graph into subsets satisfying some further requirements. First, it concerns with the existence of the partition as desired. After that, it optimizes a cost function associated with the partitions. Cayley graph, due to its simple structure and high symmetry, has attracted more attention from graph researchers, and become an important research field of graph theory. Cayley graph is often designed as the topology structure of an interconnection network. So the structural characteristics of Cayley graph, and some parameters related to the stability of networks, like connectivity and super connectivity and restricted connectivity have been studied extensively. This project focuses on the partitions of Cayley graphs with condition on the connectivity and minimum degree. For any positive integer k, we want to find a linear function f(k) such that the vertex set of every f(k)-connected Cayley graph can be partitioned into non-empty sets S and T such that the two subgraphs induced by S and T are both k-connected and every vertex in S has at least k neighbours in T.

英文关键词: partition;connectivity;minimum degree;triangle-free;

成为VIP会员查看完整内容
0

相关内容

「图分类研究」最新2022综述
专知会员服务
96+阅读 · 2022年2月13日
神经结构搜索的研究进展综述
专知会员服务
35+阅读 · 2022年1月12日
联邦学习研究综述
专知会员服务
146+阅读 · 2021年12月25日
专知会员服务
21+阅读 · 2021年9月23日
专知会员服务
23+阅读 · 2021年9月22日
专知会员服务
23+阅读 · 2021年6月9日
专知会员服务
95+阅读 · 2021年5月25日
通过条件梯度进行结构化机器学习训练,50页ppt与视频
专知会员服务
12+阅读 · 2021年2月25日
【天津大学】知识图谱划分算法研究综述
专知会员服务
106+阅读 · 2020年4月27日
清明 | 一年一清明,一岁一追思
RUC AI Box
0+阅读 · 2022年4月5日
「基于GNN的图分类研究」最新2022综述
图与推荐
7+阅读 · 2022年2月14日
「图分类研究」最新2022综述
专知
5+阅读 · 2022年2月13日
NVIDIA 招GNN加速方向实习生,GPU超多~
图与推荐
0+阅读 · 2022年1月24日
ArXiv2021 | Customized Graph Neural Networks
图与推荐
1+阅读 · 2021年12月27日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年4月20日
Arxiv
0+阅读 · 2022年4月15日
Directional Graph Networks
Arxiv
27+阅读 · 2020年12月10日
A Comprehensive Survey on Graph Neural Networks
Arxiv
13+阅读 · 2019年3月10日
小贴士
相关主题
相关VIP内容
「图分类研究」最新2022综述
专知会员服务
96+阅读 · 2022年2月13日
神经结构搜索的研究进展综述
专知会员服务
35+阅读 · 2022年1月12日
联邦学习研究综述
专知会员服务
146+阅读 · 2021年12月25日
专知会员服务
21+阅读 · 2021年9月23日
专知会员服务
23+阅读 · 2021年9月22日
专知会员服务
23+阅读 · 2021年6月9日
专知会员服务
95+阅读 · 2021年5月25日
通过条件梯度进行结构化机器学习训练,50页ppt与视频
专知会员服务
12+阅读 · 2021年2月25日
【天津大学】知识图谱划分算法研究综述
专知会员服务
106+阅读 · 2020年4月27日
相关资讯
清明 | 一年一清明,一岁一追思
RUC AI Box
0+阅读 · 2022年4月5日
「基于GNN的图分类研究」最新2022综述
图与推荐
7+阅读 · 2022年2月14日
「图分类研究」最新2022综述
专知
5+阅读 · 2022年2月13日
NVIDIA 招GNN加速方向实习生,GPU超多~
图与推荐
0+阅读 · 2022年1月24日
ArXiv2021 | Customized Graph Neural Networks
图与推荐
1+阅读 · 2021年12月27日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
微信扫码咨询专知VIP会员