权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Combinatorial Theory

组合理论

基本信息

批准号：
04302011
负责人：
ENOMOTO Hikoe
金额：
$ 5.76万
依托单位：
Keio University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Co-operative Research (A)
财政年份：
1992
资助国家：
日本
起止时间：
1992 至 1994
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-04302011/
关键词：
Combinatorics Cycles and paths of graphs Connectivity Graph embedding Algorithms Computational Geometry Spin models Association schemes 分割問題閉路次数埋め込み連結度双対グラフ指標表

项目摘要

We obtained high level results in graph theory.In particular, we proved the existence of k-facors, connected [2, k]-factors, long cycles or hamiltonian cycles assuming various kinds of connectivity (vertex-connectivity, edge-connectivity, toughness, binding number etc.). For example, we proved that with few exceptios the length of a logest cycle is at least the length of a logest path-1 if the sum of degrees of three independent vertices is at least the order of the graph. There is a strong connection between geometric properties of a surface and those of graphs enbedded in it. Geometric dual of a planar graph is well-defined, but it is not obvious what is the dual of graphs enbedded in other surfaces. We investigated duals of graphs enbedded in a projective plane. We also obtained properties of triangulations and quadrangulations of various surfaces, and decided the number of equivalence classes of such graphs under fundamental deformations. On algebraic combinatorial theory, we studied distance-regular graphs, association schemes, spin models, and Hadamard matrices. We clarified the relation of spin models and association schemes, and the properties of the character table of an association scheme. Also, we get various results on finite geometris, arrangements of lines or hyperplanes, computational geometries, and graph algorithms.

我们在图论方面取得了高层次的成果。特别是，我们证明了k-因子，连通[2，k]-因子，长环或哈密顿环的存在，假设各种连通性（顶点连通性，边连通性，韧性，结合数等）。例如，我们证明了如果三个独立顶点的度数之和至少是图的阶数，那么除了少数例外，最大循环的长度至少是最大路径-1的长度。曲面的几何性质与嵌入其中的图形的几何性质之间有很强的联系。平面图形的几何对偶是定义明确的，但嵌入在其他曲面上的图形的对偶是什么并不明显。我们研究了投影平面上图的对偶。我们还得到了各种曲面的三角剖分和四角剖分的性质，并确定了这些图在基本变形下的等价类的个数。在代数组合理论方面，我们研究了距离正则图、关联方案、自旋模型和Hadamard矩阵。阐明了自旋模型与关联方案的关系，以及关联方案的特征表的性质。此外，我们在有限几何、线或超平面的排列、计算几何和图算法上得到了各种结果。