グラフの因子構造に関する研究

Material type: 文書・図像類

Author: 藤沢, 潤

Publisher: 慶應義塾大学

Publication date: 2017

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: type:text1)次数列が3,3,3,1,1,1であるグラフをnetと呼び, netにおける次数1の頂点を端点と呼ぶ。1993年にBroersmaは「頂点数がnの2-連結クローフリーグラフGにおいて, どのinduced netも次数が(n-2)/3以上であればGはハミルトンサイクルを持つ」と予...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Keio Associated Repository of Academic resources
Digital
You can check the holdings of institutions and databases with which Institutional Repositories DataBase(IRDB)(Institutional Repository) is linked at the site of Institutional Repositories DataBase(IRDB)(Institutional Repository).
Keio Associated Repository of Academic resources

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: グラフの因子構造に関する研究
Author/Editor: 藤沢, 潤
Author Heading: 藤沢, 潤
Publication, Distribution, etc.: 慶應義塾大学
Publication Date: 2017
Publication Date (W3CDTF): 2017
Alternative Title: グラフノインシコウゾウニカンスルケンキュウ
Gurafu no inshi kōzō ni kansuru kenkyū
On factor problem in graphs
Periodical title: 学事振興資金研究成果実績報告書
Text Language Code: jpn
eng
Target Audience: 一般
Note (General): 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.
Access Restrictions: 限定公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 慶應義塾大学 : 慶應義塾大学学術情報リポジトリ