文献

J-GLOBAL ID：202202279658318883   整理番号：22A0970379

線グラフのHamilton連結性とその迂回指数への応用【JST・京大機械翻訳】

Hamilton-connectivity of line graphs with application to their detour index

著者 (3件)： Zhong Yubin (School of Mathematics and Information Sciences, Guangzhou University, Guangzhou, Guangdong, People’s Republic of China) ,  Hayat Sakander (School of Mathematics and Information Sciences, Guangzhou University, Guangzhou, Guangdong, People’s Republic of China) ,  Khan Asad (School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou, Guangdong, People’s Republic of China)
資料名： Journal of Applied Mathematics and Computing  (Journal of Applied Mathematics and Computing)
巻： 68  号： 2  ページ： 1193-1226  発行年： 2022年 
JST資料番号： W4522A  ISSN： 1598-5865  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 頂点のあらゆる対の間にハミルトニアン経路が存在するならば,グラフをHamilton結合と呼ぶ。グラフがHamilton連結であるかどうかの決定はNP完全問題である。本論文では,グラフにおけるHamilton接続性を示す2つの方法を示した。第1の方法はグラフの頂点連結性とハミルトニアン性を使用して,第2は頂点のあらゆる対の間のハミルトニアン経路を構築する定義ベースの構築方法である。これらの証明技術を用いて,一般化Petersen,反プリズムおよび車輪グラフの線グラフがHamilton連結であることを示した。いくつかの既存の結果と結合して,Hamilton連結線グラフのこれらのファミリーのいくつかが,それらの根底にあるグラフファミリー非Hamilton結合を持つことを示した。これから,Hamilton連結線グラフの根底にあるグラフは必ずしもHamilton結合ではないことを示した。サイド結果として,NP完全問題でもあるデトゥル指数をHamilton連結線グラフのファミリーに対して計算した。最後に,コンピュータによって,[数式:原文を参照]頂点に関するすべてのHamilton連結グラフと[数式:原文を参照]頂点に関するすべてのHamilton-レース可能なグラフを生成した。我々の研究は,ほぼ全てのグラフがHamilton連結であると提案した予想に寄与する。Copyright Korean Society for Informatics and Computational Applied Mathematics 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ハミルトニアン ,  *グラフ ,  プリズム ,  バイパス ,  頂点 ,  連結性 ,  NP完全問題 ,  コンピュータ
準シソーラス用語： 連結グラフ , 【Automatic Indexing@JST】

著者キーワード (8件)： グラフ ,  線グラフ ,  ハミルトニアン経路 ,  ハミルトニアンサイクル ,  NP完全問題 ,  Hamilton連結グラフ ,  Hamilton配置可能なグラフ ,  迂回指数

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

タイトルに関連する用語 (5件)： グラフ ,  連結性 ,  迂回 ,  指数 ,  応用