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

高度正则图的子结构研究

基本信息

批准号：
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因子的存在，这是一系列无限的“在3个连接的3个规范图的细分中的图形”，其中顶点的数量为3K+1，当一个点被删除时，不存在P_3因子。” 2。对于所有r，确定一组图，使得通过禁止它们获得的图为k_ {1，r}，而有限的例外。 3。通过禁止，当k为6或更少时，确定了一对两个图，以使所得的k连接图家族是有限的。 4。在圆环上4个规范图的二元图中，该图的局部变换操作“梯子陷阱”同时设计了以下两个。（1）将两部分的图形转换为不是两部分图的东西。（2）保持目标图的顶点面曲线。通过分解3偶有的3个规范图获得了1。获得的图。为阐明有关优势的芦苇预测提供了一个很好的线索。在2中获得了无限数量的图形家族数量，结果本身非常有趣，并且在2。和3中获得的研究结果将揭示哪些类型的图形家族是必不可少的，因为它是禁止的子图，为未来的研究提供了有用的信息。此外，以4的形式获得的结果提供了关于阐明圆环上两部分图的哈密顿性质的观点。通过这种方式，今年，我们取得了各种研究结果，例如“控制数”，“禁止的子图”和“封闭表面上的图形”。