文献

J-GLOBAL ID：201802211459470227   整理番号：18A0575100

樹木における二重ローマ支配【Powered by NICT】

Double Roman domination in trees

著者 (4件)： Zhang Xiujun (School of Information Science and Engineering, Chengdu University, Chengdu 610106, China) ,  Li Zepeng (School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, China) ,  Jiang Huiqin (School of Information Science and Engineering, Chengdu University, Chengdu 610106, China) ,  Shao Zehui (Research Institute of Intelligence Software, Guangzhou University, Guangzhou 510006, China)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 134  ページ： 31-34  発行年： 2018年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： SではなくGの全ての頂点がS.における少なくとも1つの近傍を持つならば,グラフGの頂点集合の部分集合Sが支配的集合である。支配数γ(G)は,全てのグラフGに対するG.A Roman支配関数の支配集合とは,各頂点は,f(u)=0は,f(v)=2少なくとも1つの頂点vに隣接しているのuという条件を満たす関数f:V(G)→{0,1,2}である間の最小濃度であると定義した。Roman支配関数の重みとは値f(V(G))=Σu∈V(G)f(u)である。グラフG上のRoman支配関数の最小重みは,そのグラフGに対するG.A二重Roman支配関数のRoman支配数γR(G)は全ての頂点は,f(u)=0は,f(ν1)=f(v2)は2f(v)=3または二頂点v1及びv2,f(u)=1は少なくとも一つの頂点に隣接した全ての頂点uが,f(v)は,≧2対少なくとも1つの頂点vに隣接しているのuという条件を満たす関数f:V(G)→{0,1,2,3}であると呼ばれる。二重Roman支配関数の重みとは値f(V(G))=Σu∈V(G)f(u)である。グラフG上の二重Roman支配関数の最小重みら(2016)G.Beelerの二重Roman支配数γdR(G)は,γ(G)≦γdR(G)≦3γ(G)とγ(T)+1≦γdR(T)≦3γ(T)任意の非自明ツリーTであることを示した,それは木のγdR(T)の値を計算するための多項式アルゴリズムを構築することが可能かどうかという問題を提起することを示したと呼ばれている。本論文では,任意の木のγdR(T)の値を計算するための線形時間アルゴリズムを与えることによりこの問題に答える。さらに,γ(T)+1=γdR(T)とγdR(T)+1=2γR(T)樹の特性化を与えた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 最小濃度 ,  部分集合 ,  *グラフ ,  キャラクタリゼーション
準シソーラス用語： 線形時間アルゴリズム ,  支配集合 ,  近傍 ,  *ローマ , 【Automatic Indexing@JST】

著者キーワード (5件)： 二重ローマ支配数 ,  ローマ支配 ,  支配数 ,  ツリー ,  組合せ問題

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 樹木 ,  ローマ ,  支配