文献

J-GLOBAL ID：201802261730447604   整理番号：18A1477742

非ハミルトニアングラフに関するErdoesの定理の拡張【JST・京大機械翻訳】

Extensions of a theorem of Erdoes on nonhamiltonian graphs

著者 (4件)： Fueredi Zoltan (Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary) ,  Kostochka Alexandr (Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801) ,  Kostochka Alexandr (Institute of Mathematics, Sobolev Institute of Mathematics, Novosibirsk 630090, Russia) ,  Luo Ruth (Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801)
資料名： Journal of Graph Theory  (Journal of Graph Theory)
巻： 89  号： 2  ページ： 176-193  発行年： 2018年 
JST資料番号： C0773B  ISSN： 0364-9024  CODEN： JGTHD  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： n,dは1≦d≦[n-12],セットh(n,d):=n-D2+d2を持つ整数である。Erは,n≧6dのとき,最小次数δ(G)≧dを有する各n頂点非ハミルトニアングラフGが,多くのh(n,d)エッジを有することを証明した。また,すべてのそのような対n,dに対して,鋭い例Hn,dを提供した。以前に,著者らはこの結果の安定性バージョンを示した:nが十分に大きい場合,δ(G)≧dとh(n,d+1)エッジを持つn頂点上のすべての非ハミルトニアングラフGはHn,dのサブグラフである。本論文において,グラフHn,dがn頂点を有する非ハミルトニアングラフの間のエッジ数を最大にするだけでなく,少なくともdを最小にすることを示した。しかし,nがdおよび|F|と比較して十分に大きい場合には,任意の固定グラフFのコピー数を最大化した。また,より強い安定性定理,すなわち,δ(G)≧dとh(n,d+2)エッジを持つすべての非ハミルトニアンn頂点グラフを分類した。著者らは,より一般的な定理を証明することによって,すべてのkに対してkのn-(d+2)k+(d+2)d+2k-1コピーをもつすべてのグラフを記述することを示した。Copyright 2018 Wiley Publishing Japan K.K. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： グラフ理論 ,  *エルビウム ,  *グラフ ,  *ハミルトニアン ,  部分グラフ
準シソーラス用語： 次数 , 【Automatic Indexing@JST】

著者キーワード (5件)： 極値グラフ理論 ,  ハミルトニアンサイクル ,  部分グラフ密度 ,  05C35 ,  05C38

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

タイトルに関連する用語 (4件)： ハミルトニアン ,  グラフ ,  定理 ,  拡張