文献

J-GLOBAL ID：201802241006003350   整理番号：18A0259929

長いサイクルのためのタイトErdoes Posa機能【Powered by NICT】

A tight Erdoes-Posa function for long cycles

著者 (4件)： Mousset F. (Department of Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland) ,  Noever A. (Department of Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland) ,  Skoric N. (Department of Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland) ,  Weissenberger F. (Department of Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland)
資料名： Journal of Combinatorial Theory. Series B  (Journal of Combinatorial Theory. Series B)
巻： 125  ページ： 21-32  発行年： 2017年 
JST資料番号： E0780A  ISSN： 0095-8956  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ErdoesとPosaの古典的な結果は,任意のグラフは,Kの頂点分離閉路を含むまたは高々O(k logk)頂点の削除による非環式であることを示した。Birmele,Bondy,ヨシ(2007)は,より一般的な問題を提起した:与えられた数LとK,全てのグラフGは,少なくともL長さのk頂点ディスジョイント・サイクルを含むまたは少なくともL長のすべてのサイクルを満たすf(l , k)頂点の集合Xを含むよう何が最適関数f(l , k)である本論文では,f(l , k)=Θ(K L+k logk)を証明することにより,この質問に答えた。当然の結果として,少なくともLを長さのk頂点分離閉路を含まない任意のグラフGの木幅はO(k L+k logk)である。は一定因子までも最適であるとBirmele,Bondy,ヨシ(2007)のもう一つの質問に答えた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *閉路 ,  グラフ
準シソーラス用語： 木幅 , 【Automatic Indexing@JST】

著者キーワード (4件)： Erdoes Posa特性 ,  被覆と充填 ,  長周期 ,  グラフ理論

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

タイトルに関連する用語 (1件)： サイクル