正則性の高いグラフの部分構造に関する研究

高度正则图的子结构研究

基本信息

批准号：
21840038
负责人：
藤澤潤
金额：
$ 1.31万
依托单位：
Kochi University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Research Activity Start-up
财政年份：
2009
资助国家：
日本
起止时间：
2009 至 2010
项目状态：
已结题

项目摘要

本研究は平成21年度より2年間科学研究費補助金の援助を受け、今年度はその初年度である。今年度得られた成果は以下の通りである。1.P_3因子の存在を保つようなグラフの変形操作を用いることにより、「3-連結3-正則グラフの細分で、頂点数が3k+1点であり、1点取り除くとP_3因子が存在しないようなグラフ」の無限系列が得られた。2.禁止することにより得られるグラフが、有限個の例外を除いてK_{1,r}フリーとなるようなグラフの族を全てのrに対して決定した。3.禁止することにより、得られるk-連結グラフの族が有限個となるような2つのグラフのペアを、kが6以下の場合に決定した。4.トーラス上の4-正則グラフの双対グラフにおいて、以下の二つを同時に満たすようなグラフの局所変形操作「ladder-addition」を考案した。(1)2部グラフであったものを2部グラフでないものに変形する。(2)対象となるグラフのvertex-face curveの存在を保つ。1.で得られたグラフは3-連結3-正則グラフを分解して得られるものであり、支配数に関するReed予想の解明のための大きな手掛かりとなる。2.で得られたグラフの族は無限個あり、その結果自体が非常に興味深い上、2.と3.で得られた研究成果によってどのようなグラフの族が禁止部分グラフの族として本質的かが解明され、今後の禁止部分グラフを用いた研究に対して有益な情報を与える。また4.で得られた成果によって、トーラス上の2部グラフのハミルトン性の解明に向けて一つの見通しが得られた。このように本年度は「支配数」「禁止部分グラフ」「閉曲面上のグラフ」といった多角的な研究成果が得られた。

这项研究从2009年开始得到了两年的科学研究资助金的支持，今年是第一年。今年获得的结果如下。 1、通过使用保留P_3因子存在性的图变换操作，可以得到顶点数为3k+1个点的3连通3正则图的细分，如果去掉一个点，P_3因子不存在，我们得到了这样的无穷级数。 2. 我们为所有 r 确定了一系列图，使得通过禁止获得的图是 K_{1,r} 自由的，但有有限数量的例外。 3. 通过禁止，我们确定了一对两个图，使得当 k 等于或小于 6 时，获得的 k 连通图的族数是有限的。 4. 在环面上的 4 正则图的对偶图中，我们设计了一种局部变形操作“梯子加法”，它同时满足以下两个条件。 (1) 将二分图变换为非二分图。 (2) 维持目标图的点面曲线的存在性。 1.中得到的图是通过分解3连通3正则图得到的，是阐明关于主导数的里德猜想的重要线索。 2.中获得的图族有无限多个。结果本身就非常有趣，并且2.和3.中获得的研究结果揭示了什么样的图族作为禁止子图族是必要的，这将提供有用的信息。使用禁止子图进行未来研究的信息。此外，第 4 节中获得的结果为阐明环面上二部图的哈密顿性质提供了前景。就这样，今年我们获得了“支配数”、“禁止子图”、“闭曲面上的图”等多方面的研究成果。