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

密なグラフの構造把握のための連結度と禁止部分グラフに関する研究

研究连通性和禁止子图以理解稠密图的结构

基本信息

批准号：
18740059
负责人：
藤田慎也
金额：
$ 1.86万
依托单位：
Gunma National College of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2007
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18740059/
关键词：
グラフの連結度禁止部分グラフ点素な部分グラフの存在

项目摘要

今年度は前年度に引き続き,点素な星グラフの存在に関する江川-太田予想の解決にむけて禁止部分グラフの観点から研究を進めた。その結果,以下の定理を得ることが出来,今年度Discrete Mathematicsに論文として出版された.定理.kを2以上め整数とする.位数7-6上,最小次数3以上のK_<1,3>を誘導部分グラフとして含まない任意のグラフは点素なK_1+(K_1UK_2)をk個含む.この定理における位数・最小次数の条件はともに最善であり,H.Wangによって得られていたK_<1,3>を誘導部分グラフとして含まないグラフの族における点素な三角形の存在に関する結果の位数が大きいときの拡張にもなっている.さらに,この結果は,研究代表者が提起したK_<1,t>を誘導部分グラフとして含まないグラフのクラスにおける同様の問題に関する部分的解決を与えており,禁止部分グラフのこの種の極値問題研究に関して新たな進展を与えたと言える.また,密なグラフの内部では,グラフめ連結度が部分的に高くなり,そのような高連結部分グラフの構造把握の重要性から,本研究ではグラフの連結度に関しても並行して研究を進めていた.その結果,除去しても連結度が下がらないような辺が存在するための十分条件としてのグラフの次数条件についてもほぼ最善の値を決定することに成功した.さらに,禁止部分グラフの研究と関連して,縮約しても連結度が下がらない辺もしくは三角形が存在するための禁止部分グラフを決定するという問題に対しても新しい結果を得ることが出来,Journal of Graph Theoryに論文として出版された.

This year's research on the relationship between the existence of star power and the prohibition of star power has been carried out. The following theorem is obtained and published in Discrete Mathematics. Theorem.k is more than 2. K_<1,3>, the minimum number of times, is more than 3, and K_1 +(K_1UK_2) is k. H.Wang's theorem is based on the condition that the number of digits and the minimum degree are optimal. In this paper, the results show that the research representatives have raised the issue of K_<1,t> induction, partial solution of the same problem, partial solution of the same problem, and partial solution of the same problem. The importance of structural understanding of the high degree of connectedness of some parts of the structure. As a result, except for the link degree, there are very good conditions for the existence of the link degree, and the number of times the link degree is determined. In addition, the Journal of Graph Theory published a paper on the study of the relationship between the forbidden part and the link degree.