文献

J-GLOBAL ID：202202277072322425   整理番号：22A0797077

強エッジ彩色グラフのレインボーエッジ-パンサイクリック性【JST・京大機械翻訳】

Rainbow edge-pancyclicity of strongly edge-colored graphs

著者 (2件)： Li Luyi (Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China) ,  Li Xueliang (Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 907  ページ： 26-33  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： エッジカラーグラフGにおいて,すべてのエッジが異なる色を持つならば,部分グラフは rainbowである。強いエッジ色グラフは,長さ3の各々の経路が rainbowであるエッジカラーグラフである。次数nのエッジ色グラフGにおけるサイクルCは,サイクルが rainbowで,その長さがnであるならば, rainbowハミルトニアンサイクルと呼ばれる。次数nのエッジ色グラフGは,Gの各頂点(エッジ)が3≦k≦nで各kに対して長さkの rainbow周期に含まれているならば, rainbow頂点(エッジ)-パンサイクリックである。2019年のChengらは,最小次数ε′′2n3の次数nのあらゆる強いエッジ色グラフGが, rainbowハミルトニアンサイクルを含むことを示した。2021年には,Wangらは,この結果を拡張し,最小次数ε>2n3の次数nのあらゆる強いエッジ色グラフGが, rainbow頂点-非環状であることを示した。本論文では,さらに,最小次数|≦2n+13の次数nのあらゆる強いエッジ色グラフGが, rainbow端-非環状であることを示した。さらに,この証明から,エッジeを含む各3≦l≦nに対する rainbowのlサイクルを見つけるために,任意のそのようなグラフGにおいて任意のエッジeに対して多項式時間アルゴリズムを得た。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ハミルトニアン ,  *グラフ ,  部分グラフ ,  *発色 ,  *端部 ,  頂点
準シソーラス用語： 多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (4件)： ニジマス ,  強エッジ彩色グラフ ,  レインボーハミルトニアンサイクル ,  レインボー頂点(エッジ)-パンサイクル

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

タイトルに関連する用語 (4件)： エッジ ,  彩色 ,  グラフ ,  レインボー