文献

J-GLOBAL ID：201802267708220091   整理番号：18A0128373

最大外平面グラフの安全な支配数について【Powered by NICT】

On the secure domination numbers of maximal outerplanar graphs

著者 (2件)： Araki Toru (Division of Electronics and Informatics, Gunma University, Kiryu, Gunma 376-8515, Japan) ,  Yumoto Issei (Division of Electronics and Informatics, Gunma University, Kiryu, Gunma 376-8515, Japan)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 236  ページ： 23-29  発行年： 2018年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： SがGの支配集合であり,各頂点u/∈S,U vは辺が存在するような,頂点v∈Sであり(S \ { v })∪{u}もGの支配集合ならばグラフG中の頂点の部分集合SがGの安全な支配集合である。Gをn頂点の最大outerplaneグラフであるならば,Gは最も[3n/7]のサイズの安全な支配集合を持つことを示した。さらに,最大outerplaneグラフGが内部三角形を持たないならば,それは最も[n/3]のサイズの安全な支配集合を持っている。最後に,内部三角形を持たない最大outerplaneグラフの安全な支配集合はn/4よりもより多くの頂点を持つことを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *平面グラフ ,  *安全性 ,  *グラフ ,  部分集合
準シソーラス用語： 支配集合 , 【Automatic Indexing@JST】

著者キーワード (4件)： 安全な支配 ,  最大外平面グラフ ,  上限 ,  下限

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

タイトルに関連する用語 (2件)： 平面グラフ ,  支配