文献

J-GLOBAL ID：202402265017365000   整理番号：24A0739253

ラプラシアン行列の固有値を用いた木幅の下界

著者 (5件)： 儀間達也 (名古屋大) ,  土中哲秀 (九大) ,  野呂浩平 (名古屋大) ,  小野廣隆 (名古屋大) ,  大舘陽太 (名古屋大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2024  号： AL-197  ページ： Vol.2024-AL-197,No.6,1-2 (WEB ONLY)  発行年： 2024年03月14日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では頂点数n,最大次数ΔのグラフGについて,ラプラシアン行列の固有値を用いた木幅tw(G)の下界を二つ示す.一つはラプラシアン行列の二番目に小さい固有値λ₂を用いた下界で,tw(G)≧A-1(A=nλ₂/Δ+λ₂)が成り立つ,というものである.これはChandranとSubramanian[A spectral lower bound for the treewidth of a graph and its consequences.Inf.Process.Lett.,87(4):195-200,2003]によって示された下界tw(G)≧3nλ₂/(4Δ+8λ₂)-1の改善となっている.今回示した下界は,特に完全二部グラフK_a,bに対してはtw(K_a,b)≧min{a,b}-1を与え,K_a,bの実際の木幅tw(K_a,b)=min{a,b}よりちょうど1だけ小さい値となっている.もう一つはラプラシアン行列の二番目に小さい固有値λ₂および一番大きい固有値λ_nを用いた下界で,tw(G)≧B-1(B=2nλ₂/3λ_n-λ₂)が成り立つ,というものである.この下界は完全グラフK_nに対してtw(K_n)≧n-1を与える.これはK_nの実際の木幅tw(K_n)=n-1と一致する.(著者抄録)

シソーラス用語： *幅 ,  *行列 ,  *固有値 ,  限界 ,  部分グラフ ,  グラフ理論 ,  パラメータ ,  NP困難 ,  下界
準シソーラス用語： *Laplacian行列 ,  NP困難問題 ,  二部グラフ ,  *木幅

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： ラプラシアン行列 ,  固有値 ,  木幅 ,  下界