Ore型条件をともなった一般のグラフ及び2部グラフのサイクル分割について

关于矿石类型条件下一般图和二分图的循环划分

• 批准号: 14740087
• 负责人: 善本 潔
• 金额: $ 1.66万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14740087/
• 关键词: Ore条件; 支配的サイクル; 2因子; 三角形自由グラフ; 線グラフ; 関連距離; 二部グラフ; 三角形フリーグラフ; Ore型条件; ハミルトンサイクル; 辺次数; 2部グラフ; 最長サイクル; 支配的なサイクル; 連結度

支配的サイクルとは、グラフからそのサイクル上の頂点を取り除くと孤立点が残るサイクルである。支配的サイクルは、ハミルトンサイクルの一般化となっている。榎本らは、B0ndyの支配的サイクルに関する結果を拡張して、関連距離に関する主張を得た。関連距離とは、最長サイクルの長さと最長パスの長さの差である。本研究者はまず三角形自由なグラフの関連距離の研究を行い、最小次数が(|G|+2)/4以上ある三角形自由グラフGに対して、任意のパス上の高々1頂点をのぞいて、パス上のすべての頂点を通るサイクルが存在するか、または位数の小さい例外のグラフと同型であることを示した。この結果の系として、関連距離が1以下であることが容易にわかる。さらにこの主張を使い、上と同じ条件の元、高々最小時数個の任意に指定された頂点に対して、それを通るサイクルの存在について示した。上の榎本らの主張は、最小次数が(|G|+2)/3以上の2連結グラフの関連距離が1以下であることを主張している。本研究者は、この主張を一般化し、最小次数の条件を(|G|+3)/4に緩めた場合、関連距離が2以下であることを示した。この主張は、上の三角形自由グラフの場合と同様に、任意のパスに対して、高々隣接する2頂点をのぞいて、すべての頂点を通るサイクルが存在するか、またはそのグラフはハミルトンパスを持つことを示した。この結果は、SchierneyerとTewesの結果を改良している。この主張から、任意の指定された高々最小次数-1個の頂点に対して、それらを通るサイクルがあるか、ハミルトンパスを持つことがわかる。線グラフの2因子についての研究は、そのハミルトン性の研究に関連して最近多くの研究者によって多彩な成果が得られている。一般に、線グラフはK3自由なグラフであり、2因子の存在についての結果も、K3自由なグラフに対するより一般的な結果として江川・大田によって示されている。この結果より、最小次数が3以上あるグラフの線グラフは2因子を持つことが容易にわかる。本研究者は、その2因子の連結成分の数の上限を与えた。すなわち、最小次数が3以上のグラフの線グラフは、高々(3|G|-2)/8個の連結成分からなる2因子を持つことを示した。一般に、最小次数が2以下になると、多くのグラフの線グラフが2因子を持たない。本研究者は、奇ブランチ・バンドと呼ばれるグラフの不変量が1以下ならば、上と同様の主張が成り立つことを示した。最小次数が3以上ならば、この不変量は自動的に1以下になる。この場合、上の連結成分の上限は、最良の値になる。

Dominated Dominated by The results of this paper are as follows: 1. The relationship between the distance and the dominance of B0 ndy is as follows: The distance between them is the longest distance between them. This paper presents a study on the correlation distance of triangular free space.| G| + 2)/4 + 3 + 4 + The result of this is that the correlation distance is less than 1. In this case, the minimum number of arbitrary specified vertices shall be determined according to the conditions of the middle, upper and lower classes. The minimum number of times that the original idea is reversed (|G| +2)/3 or more of the 2 links are linked to each other and the distance between them is less than 1. The researcher generalizes the proposition and the condition of minimum frequency.| G| +3)/4 This proposition is based on the fact that the triangle is free to rotate, and the triangle is free to rotate. Schierneyer and Tewes improved their results. The minimum number of times that the claim is made, the arbitrary designation is made, and the maximum number of times is-1. The research on the 2 factors of linear regression is related to the research on the characteristics of linear regression. Recently, many researchers have made great achievements in this field. General, line K3 free, 2 factors exist in the results, K3 free, line K3 free. The result is, the minimum number of times is more than 3. The researchers found that the upper limit of the number of link components of the two factors was different from that of the two factors. The minimum number of times is more than 3. The number of times is more than 3| G|-2)/8 link components 2 factor In general, if the minimum number of times is less than 2, the number of clicks and line clicks can be maintained by a factor of 2. This researcher has shown that there is no difference between 1 and 2 in terms of the number of unique characters and the number of unique characters in terms of the same characters. The minimum number of times is more than 3, and the number of times is less than 1. In this case, the upper limit of the link component is opposite, and the best value is opposite.

项目成果

Contractible edges and bowties in a k-connected graphs

k 连接图中的可收缩边和领结

• 发表时间: 2002
• 期刊: Ars Combin. 64
• 作者: K.Ando;A.Kaneko K.Kawarabayashi;K.Yoshimoto
• 通讯作者: K.Yoshimoto

A.Kaneko, K.Yoshimoto: "On a 2-Factor with a Specified Edge of a Graph Satisfying the Ore Condition"Discrete Math.. 257. 445-461 (2002)

A.Kaneko、K.Yoshimoto：“关于满足矿石条件的图的指定边的 2 因子”离散数学.. 257. 445-461 (2002)

A.Kaneko, K.Yoshimoto: "A 2-factor with two components of a graph satisfying the Chvatal-Erdos condition"J.Graph theory. 43. 269-279 (2003)

A.Kaneko，K.Yoshimoto：“图的两个分量满足 Chvatal-Erdos 条件的 2 因子”J.Graph Theory。

On a 2-Factor with a Specified Edge of a Graph Satisfying the Ore Condition

关于满足矿石条件的图的指定边的2-因子

• 发表时间: 2002
• 期刊: Discrete Math. 257
• 作者: A.Kaneko;K.Yoshimoto
• 通讯作者: K.Yoshimoto

On geometric independency trees of the set of points in the plane

平面上点集的几何独立树

• 发表时间: 2002
• 期刊: Discrete Math. 258
• 作者: Kaneko;Y.Oda;K;Yoshimoto
• 通讯作者: Yoshimoto