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

高度正则图的子结构研究

• 批准号: 21840038
• 负责人: 藤澤 潤
• 金额: $ 1.31万
• 依托单位: Kochi University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21840038/
• 关键词: グラフ; 正則グラフ; 局所変形操作; 支配数; 禁止部分グラフ; 位相幾何学的グラフ理論

本研究は平成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部グラフのハミルトン性の解明に向けて一つの見通しが得られた。このように本年度は「支配数」「禁止部分グラフ」「閉曲面上のグラフ」といった多角的な研究成果が得られた。

This research was funded by the Scientific Research Grant for the first two years of 2011, and this year it was funded by the Scientific Research Grant for the first two years of 2011. This year's results are as follows. 1. The infinite series of "3-link 3-regular subdivision, vertex number 3k +1, 1-point division" of P_3 factor is obtained. 2. A limited number of exceptions to this rule are required. 3. It is forbidden to determine the number of k-links in the family when k is less than 6. 4. A case of "ladder-addition" is considered for the 4-regular shift on the first shift and the double shift on the second shift at the same time. (1)2 The two parts of the book are the same. (2)The existence of a vertex-face curve is guaranteed. 1. Get a 3-link 3-regular 3-link 3-link 2. To obtain the results of the research, to obtain the results of the research. 4. The results of the study were obtained through the study of the relationship between the two groups. This year, the research results of "dominant number","forbidden part" and "closed surface" were obtained.

项目成果

トーラス上の四角形分割におけるハミルトンサイクルの存在について

关于圆环上四边形除法中汉密尔顿循环的存在性

• 发表时间: 2010
• 作者: K.Gomi;Twisted;藤沢潤
• 通讯作者: 藤沢潤

Lambda-backbone Colorings along Pairwise Disjoint Stars and Matchings

• DOI: 10.1016/j.disc.2008.04.007
• 发表时间: 2009-09
• 期刊: Discret. Math.
• 作者: H. J. Broersma;J. Fujisawa;B. Marchal;D. Paulusma;A. Salman;Kiyoshi Yoshimoto

Two forbidden subgraphs and the existence of a 2-factor in graphs

两个禁止子图以及图中 2 因子的存在性

• 发表时间: 2009
• 期刊: Australas. J. Combin
• 作者: R. E. L. Aldred;J. Fujisawa and A. Saito
• 通讯作者: J. Fujisawa and A. Saito