並列タイトル等グラフ ノ インシ コウゾウ ニ カンスル ケンキュウ
Gurafu no inshi kōzō ni kansuru kenkyū
On factor problem in graphs
一般注記出版タイプ： VoR
type:text
1)次数列が3,3,3,1,1,1であるグラフをnetと呼び, netにおける次数1の頂点を端点と呼ぶ。1993年にBroersmaは「頂点数がnの2-連結クローフリーグラフGにおいて, どのinduced netも次数が(n-2)/3以上であればGはハミルトンサイクルを持つ」と予想したが, その予想が肯定的に解決された。
2)グラフGとマッチングMに対して, Mを含むようなGの完全マッチングが存在する時, Mは拡張的であると言う。また, グラフ上の2辺間の距離をその2辺を結ぶ最短のパスの長さで定義し, あるグラフのマッチングMに対し, M内のどの2辺も距離がd以上離れている時, Mをdistance dマッチングと呼ぶ。さらに, グラフGの任意のdistance dマッチングが拡張的となる時にGはdistance d matchableであると言う。近年のマッチング拡張の研究の中で提起された「"G ∈ Xならば, Gはdistance d matchableである"という定数dが存在するようなグラフの族Xにはどのようなものがあるか」という問題は, 拡張する辺の本数に上限がないという点で既存の研究と一線を画し, 興味深い。その中で, 「3-連結3-正則2部グラフで, 任意の辺eに対しE(C_1)∩E(C_2) = {e}であるような長さd 以下のサイクルC_1, C_2 が存在するもの」が上記のXに含まれることが示された。
1) The connected graph of degree sequence 3,3,3,1,1,1 is called a net, and the vertices of degree 1 in a net is called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K_{1,3} is hamiltonian if every endvertex of each induced net of G has degree at least (|V(G)|-2)/3 ; this conjecture is proved in the affirmative.
2) A matching M of a graph G is said to be extendable in G if M is a subset of a perfect matching in G. A graph is said to be distance d matchable if any matching in which the edges lie pair-wise distance at least d is extendable. This property is of interest because we don't need to care about the number of edges to extend, and the the study of distance d matchable graphs gives a new perspective which is not discussed in the traditional study of matching extension. Here the following result is shown : Let G be a 3-connected cubic bipartite graph. If for each e∈E(G), there exists two cycles C_1, C_2 of length at most d such that E(C_1)∩E(C_2)={e}, then G is distance d matchable.
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）