極値グラフ理論的観点による完全多部グラフマイナーのスペクトラム解析

点击翻译按钮获取中文摘要

本研究の目的は極値グラフ理論的観点から完全多部グラフマイナーのスペクトラム解析である．目的達成のため，本研究では辺の本数が頂点数に比べて多いグラフ（密なグラフ）の構造解析，そして，平面的グラフに関する研究を行った．以下，本研究に関係する結果の詳細を記載する．1つ目の結果は平面的グラフが(m,n)-linkedであるための必要十分条件を与えたものである．既存の結果では平面的グラフが(3,3)-linkedであるための必要十分条件を与えていたが，本研究ではその一般化に成功している．頂点数の少ないグラフのマイナーを見つける際には，対象となるグラフに平面的グラフに近い性質が出てくることがある．そのため，本研究は頂点数の少ないグラフのマイナーを見つける研究と関連している．本研究成果は国際誌Graphs and Combinatoricsに受理されている．2つ目の結果は辺連結度の高いグラフには任意の向き付けから，辺のフリップ操作によって辺連結度を下げることなく，高い辺連結度の有向グラフにすることができることを示している．これはグラフ間の構造解析を行ったものであり，本研究課題のスペクトラム解析にも関連する．本研究成果は査読付き国際会議Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithmsと国際誌ACM Transactions on Algorithmsにすでに受理されている．また，このほかにも査読付き国際誌に1本の論文が受理されており，査読付き国際会議に4つの結果が受理されている．さらに，現在，査読付き国際誌に3編の論文を投稿中である．