文献

J-GLOBAL ID：201802277848180145   整理番号：18A0279118

グラフのレインボーk接続のための困難性結果【Powered by NICT】

Hardness result for the total rainbow k-connection of graphs

著者 (4件)： Li Wenjing (Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, PR China) ,  Li Xueliang (Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, PR China) ,  Li Xueliang (Department of Mathematics, Qinghai Normal University, Xining, Qinghai 810008, PR China) ,  Wu Di (Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, PR China)
資料名： Applied Mathematics and Computation  (Applied Mathematics and Computation)
巻： 305  ページ： 27-31  発行年： 2017年 
JST資料番号： D0568B  ISSN： 0096-3003  CODEN： AMHCBQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGの全彩色とはGの辺集合E(G)と頂点集合V(G)の両方の彩色であるエッジと内部頂点が個別の色を持つならば,全カラーグラフにおける経路は全レインボーと呼ばれている。正整数kに対して,Gの全ての二頂点がそれらを連結するGのk内部互いに素な全レインボー経路であるならば,全カラーグラフは全レインボーk連結と呼ばれる。l連結グラフGと整数kを1≦k≦Lに対して,Gの全レインボーk連結数,trc_k(G)によって記されるG全レインボーk連結をGの全彩色に必要な色の最小数である。本論文では,グラフのレインボーk連結数の計算量を調べた。は,固定正整数のrc(G)=3かどうかを決定するNP完全であることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 計算量 ,  発色 ,  *グラフ
準シソーラス用語： 連結グラフ ,  互いに素 , 【Automatic Indexing@JST】

著者キーワード (3件)： 全レインボーk接続数 ,  計算の複雑さ ,  NP完全

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

タイトルに関連する用語 (3件)： グラフ ,  レインボー ,  困難性