文献

J-GLOBAL ID：201402276302339098   整理番号：14A0513968

k-支配グラフ

The k-Dominating Graph

著者 (2件)： HAAS R. (Smith Coll., Dep. of Mathematics and Statistics, 01063, Northampton, MA, USA) ,  SEYFFARTH K. (Univ. of Calgary, Dep. of Mathematics and Statistics, T2N 1N4, Calgary, AB, CAN)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 30  号： 3  ページ： 609-617  発行年： 2014年05月 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 与えられたグラフGに対して,Gのk-支配グラフD_k(G)はその頂点が高々kの濃度を持つGの支配集合に対応するグラフとして定義される。D_k(G)中の2つの頂点は単一頂点の追加あるいは除去いずれかによってGの対応する支配集合が異なる時に限って隣接している。グラフD_k(G)は支配集合に対する再構成問題の研究を助ける。特に,各段階での頂点の中間集合がそれらがD_k(G)の同一連結成分中にある時に限って支配集合であるような単一頂点の追加及び除去の系列によって1つの支配集合を別のものへと再構成できる。本論文において,筆者らはD_k(G)が連結である事を保証する条件を与えた。Copyright 2013 Springer Japan Translated from English into Japanese by JST.

シソーラス用語： グラフ理論 ,  *集合 ,  *グラフ ,  *再構成 ,  連結性 ,  部分グラフ
準シソーラス用語： 二部グラフ ,  *支配集合

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

引用文献 (14件)：

• Berge, C.: Some classes of perfect graphs. In: Six Papers in Graph Theory. Indian Statistical Institute, McMillan, pp. 1-21 (1963)
• Bonsma P., Cereceda L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci. 410(50), 5215-5226 (2009)
• Bondy, J.A., Murty, U.S.R.: Graph Theory. GTM 244, Springer, Berlin (2008)
• Cereceda L., Heuvel J., Johnson M.: Connectedness of the graph of vertex-colourings. Discrete Math. 308, 913-919 (2008)
• Cereceda L., Heuvel J., Johnson M.: Finding paths between 3-colorings. J. Graph Theory 67, 69-82 (2011)

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