Embedding and Partition of Graphs

图的嵌入和划分

• 批准号: 14540134
• 负责人: ENOMOTO Hikoe
• 金额: $ 2.18万
• 依托单位: HIROSHIMA UNIVERSITY (2003-2004)Keio University (2002)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14540134/
• 关键词: graph; cycle; factor; decree condition; independence number; connectivity; 次数条件; 因子分解; (g, f)-因子; 分割; 孤立点; 成分因子; 彩色数; リスト彩色数; 直径

(1)In 1997, Brandt and others proved that a graph G of order at least 4k and the degree sum of nonadjacent vertices at least |V(G)| can be partitioned into k disjoint cycles. This result is generalized in several ways. We weakened the degree sum assumption to |V(G)|-k+1 by allowing degenerated cycles (edges and isolated vertices). We also obtained sufficient conditions on the minimum degree to assure that each cycle passes through a specified vertex. We also solved the problem in which each cycle passes through a specified vertex or a specified edge. Furthermore, we solved the problem for bipartite graphs.(2)Erdos-Chvatal theorem says that if the independence number is not larger than the connectivity, the graph contains a Hamiltonian cycle. We generalized this result to the existence of a long cycle.(3)We investigated the maximum order of a graph without k disjoint cycles and the independence number is at most α.(4)We proved that if G is an (mg+m-1,mf-m+1)-graph and if k≦g(x)≦f(x) for any vertex x of G,G can be factorized into (g,f)-factors in which each factor contains k specified edges.

(1)In 1997年，Brandt等人证明了一个阶至少为4k且不相邻点的度和至少|V（G）|可以被划分为k个不相交的循环。这一结果在几个方面得到推广。我们弱化了度和假设，|V（G）|-k+1通过允许退化的循环（边缘和孤立的顶点）。我们还得到了最小度的充分条件，以确保每个循环通过一个指定的顶点。我们还解决了每个循环通过指定顶点或指定边的问题。此外，我们解决了二部图的问题。（2）Erdos-Chvatal定理：如果图的独立数不大于连通数，则该图包含一个Hamilton圈。我们把这个结果推广到长圈的存在性。(3)We研究了不含k个不相交圈且独立数至多为α的图的最大阶. (4)We证明了如果G是（mg+m-1，mf-m+1）-图，且对G的任意顶点x，k ∈ g（x）∈ f（x），则G可分解为（g，f）-因子，其中每个因子包含k条指定边.

项目成果

Practical fast algorithm for finite field arithmetics using groupings

使用分组进行有限域算术的实用快速算法

• 发表时间: 2004
• 期刊: Hiroshima Math.J. 34
• 作者: M.Matsumoto;S.Tagami
• 通讯作者: S.Tagami

R.Mori, A.Nakamoto, K.Ota: "Diagonal Flips in Hamiltonian Triangulations on the Sphere"Graphs and Combinatorics. 19. 413-418 (2003)

R.Mori、A.Nakamoto、K.Ota：“球面上哈密顿三角剖分中的对角线翻转”图形和组合。

Diagonal Flips in Hamiltonian Triangulations on the Sphere

• DOI: 10.1007/s00373-002-0508-6
• 发表时间: 2003-11
• 期刊: Graphs and Combinatorics
• 影响因子: 0.7
• 作者: Ryuichi Mori;Atsuhiro Nakamoto;K. Ota

Vertex‐disjoint cycles containing specified vertices in a bipartite graph

• DOI: 10.1002/jgt.10159
• 发表时间: 2004-07
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Guantao Chen;H. Enomoto;K. Kawarabayashi;K. Ota;Dingjun Lou;Akira Saito

Y.Egawa, H.Enomoto, N.Tokushige: "Graph decompositions through prescribed vertices without isolates"Ars Combinatoria. 62. 189-205 (2002)

Y.Ekawa、H.Enomoto、N.Tokushige：“通过没有孤立点的指定顶点进行图分解”Ars Combinatoria。