一般化Kneserグラフのツリー幅について【JST・京大機械翻訳】

Metsch Klaus

プレプリント

J-GLOBAL ID：202202213663746152 整理番号：22P0310686

一般化Kneserグラフのツリー幅について【JST・京大機械翻訳】

On the treewidth of generalized Kneser graphs

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2022年03月26日プレプリントサーバーでの情報更新日： 2022年03月26日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

整数k>t>0とn>2k-tの一般化KneserグラフK(n,k,t)は,頂点がt要素より少ない場合のみ,2つの頂点を持つ{1,s,n}のk部分集合であるグラフである。t≧2とnがkと比較して十分に大きいとき,一般化KneserグラフK(n,k,t)の木幅を決定した。nに束縛された結合は,以前に知られている結合の有意な改善である。著者らの結果の1つの結果は以下の通りである。各整数c≧1では,k≧K(c)がt=k-c(t=k-c)がt=k-c(t=k(n,k,t)=(nk)-(n-tk-t)-1),もしn≧(t+1)(k+1-t)の場合だけ,k≧K(c)の定数K(c)≧2cが存在する,という定数K(c)≧2cが存在する。【JST・京大機械翻訳】

, , ,
, 【Automatic Indexing@JST】

グラフ理論基礎

前のページに戻る