助成番号

５－２180665
研 究 成 果 報 告 書

研究テーマ
（和文）

フラーレンと 2 種類の面を持つ 3-正則平面グラフに関する研究

研究テーマ
（英文）

On fullerenes and 3-regular plane graphs with 2 types of faces

研究期間

２０１８

研究代表者

（漢字）

土屋 翔一

（カタカナ）

ツチヤ ショウイチ

（英文）

Shoichi Tsuchiya

氏
名年 ～ ２０２１

年

研究機関名

専修大学

所属機関・職名（漢字）

共同研究者（１名をこえる場合は、別紙追加用紙へ）

氏
名（カタカナ）（英文）所属機関・職名
概要 （600 字～800 字程度にまとめてください。）
新型コロナウイルスの影響で，研究計画の調整が必要となったものの，次数 2 の頂点を持たない全域木(HIST)や次数 2 の頂点を持たない木(HIT)について，次のような成果が得られた．
(1) HIST の存在性を保証するための次数和条件．
様々なグラフについて，その存在性を保証するための最小次数条件や次数和条件を求める研究が進められている．Albertson たちは頂点数 n の連結グラフの最小次数が以上であれば，そのグラフは HISTを持つことを示した．一方，HIST の存在を保証するための次数和条件は得られていなかった．本研究では，特定の頂点からの距離構造に着目することにより，頂点数 n のグラフ（n≧8）の非隣接 2 頂点の次数和が n-1 以上であれば，そのグラフは HIST を持つことを証明した．また，n-1 という値の最善性も示した．この成果は，Journal of Graph Theory に掲載された．
(2) Path free graph における HIT の頂点数．
特定の長さの induced path を含まないグラフを path free graph とよび，特に n 頂点の induced pathを含まないグラフを Pn-free graph とよぶ．既存研究で連結な P4-free graph や連結な P5-free graph については，HIST を持つための必要十分条件が示されていた．これらの結果から，連結な P4-free graphや連結な P5-free graph はある程度の大きさの HIT を持つことが示せる．本研究では，任意の n（n ≧6）について，Pn-free graph はある程度の大きさの HIT を持つことを示した．特に，n=6, 7 の場合は，得られる HIT の頂点数がもとのグラフの頂点数の一次関数で表せることが証明できた．この成果は，Journal of Graph Theory に掲載された．
これらの成果を改良することで，直径の短いグラフにおける HIST や HIT の存在性が議論できると考えているので，今後の研究課題として進めていく予定である．

- 1 -発表文献 （この研究を発表した雑誌・図書について記入してください。）
論文課題

Degree sum conditions for the existence of Homeomorphically Irreducible Spanning Trees

著者名

Taisei Ito,
Shoichi Tsuchiya

雑誌名Journal of Graph Theoryページ

162～170

発行年

2

雑誌

022巻号

論文課題

Large homeomorphically irreducible trees in path-free graphs

著者名Michitaka Furuya,
Shoichi Tsuchiya

雑誌名Journal of Graph Theoryページ

372～394

発行年

299

雑誌

020巻号

93

論文課題
雑誌

著者名
ページ

雑誌名
～

発行年

巻号

発行年

総ﾍﾟｰｼﾞ

発行年

総ﾍﾟｰｼﾞ

書名
図書

著者名
出版社
書名

図書

著者名
出版社

英文抄録 （100 語～200 語程度にまとめてください。）(1) Degree sum conditions for the existence of Homeomorphically Irreducible Spanning Trees.
In graph theory, there are a lot of researches on minimum degree conditions and degree sum conditions
for the existence of a special graph. Albertson et al. proved a theorem on the minimum degree ofconnected graphs for the existence of a homeomorphically irreducible spanning tree (HIST), where HIST
is a spanning tree with no vertices of degree 2. In this paper, we prove that for a connected graph
G of order n（n≧8）, if the degree sum of any nonadjacent vertices of G is at least n-1, then G
contains a HIST. We also show that “n-1”of this theorem is best possible.
(2) Large homeomorphically irreducible trees in path-free graphs．
A graph is called a Pn-free graph if it contains no induced path of order n. There are theorems
which characterize connected P4-free graphs and connected P5-free graphs to have a HIST. In thispaper, we prove that for each integer n（n ≧6）, every Pn-free graph contains a homeomorphicallyirreducible tree (HIT) of order f(n), where HIT is a tree with no vertices of degree 2. In particular,
we prove that f(n) is a linear function when the case n=6, 7.

- 2 -研究代表者名

土屋 翔一

（漢字）

共同研究者
氏名（カタカナ）（英文）所属機関・職名（漢字）
氏
名（カタカナ）（英文）所属機関・職名（漢字）
氏
名（カタカナ）（英文）所属機関・職名（漢字）
氏
名（カタカナ）（英文）所属機関・職名（漢字）
氏
名（カタカナ）（英文）所属機関・職名（漢字）
氏
名（カタカナ）（英文）所属機関・職名（漢字）
氏
名（カタカナ）（英文）所属機関・職名（漢字）
氏
名（カタカナ）（英文）所属機関・職名- 3 -