文献

J-GLOBAL ID：201702268190379233   整理番号：17A0963108

木のユニット超立方体可視度数

Unit Hypercube Visibility Numbers of Trees

著者 (2件)： PETERSON Eric (Univ. Rhode Island, RI, USA) ,  WENGER Paul S. (Rochester Inst. Technol., NY, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 4  ページ： 1023-1035  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Rⁿのユニット超立方体に割り当てられた頂点を包含する可視度表現を研究した。Rⁿの基本として,標準基本ベクトルe₁,...,e_nを,終始使用した。ユニットバー可視度グラフとユニット長方形可視度グラフに触発されて,可視度の2つのバージョンを使った。頂点がユニット超立方体の集合に配置されたときの,木の可視度数を研究した。Gのn可視度表現になるように,グラフGのn立方体可視度数:hⁿ(G)は,最小のtである。Gの各頂点は,Rⁿの中で最多のtユニットn立方体になるように配置されている。Gのn立方体直交可視度表現が存在するように,グラフGのn立方体直交可視度数:h^(n)⊥(G)は,最小のtである。Gの中で各頂点は,Rⁿ⁺¹の中で最大のtのn立方体になるように配置されている。結論として,次の研究への課題として,疑問を3項目記載した。

シソーラス用語： *多面体 ,  *木【グラフ】 ,  *可視度 ,  数 ,  頂点 ,  配置問題 ,  長方形
準シソーラス用語： *超立方体

分類 (1件)： 集合論  (AB10000I)

引用文献 (24件)：

• Axenovich, M., Beveridge, A., Hutchinson, J.P., West, D.B.: Visibility number of directed graphs. SIAM J. Discret. Math. 27(3), 1429-1449 (2013)
• Babu, J., Basavaraju, M., Chandran, L.S., Rajendraprasad, D., Sivadasan, N.: Approximating the Cubicity of Trees. arXiv:1402.6310 [cs.DM]
• Bose, P., Dean, A., Hutchinson, J., Shermer, T.: On rectangle visibility graphs. In: North, S. (ed.) Lecture Notes in Computer Science 1190: Graph Drawing, pp. 25-44. Springer, Berlin (1997)
• Buneman, P.: A characterisation of rigid circuit graphs. Discret. Math. 9, 205-212 (1974)
• Chang, Y., Hutchinson, J.P., Jacobson, M.S., Lehel, J., West, D.B.: The bar visibility number of a graph. SIAM J. Discret. Math. 18(3), 462-471 (2004)

タイトルに関連する用語 (3件)： 木 ,  超立方体 ,  可視度