文献

J-GLOBAL ID：201702280811256880   整理番号：17A0522420

リラックスグレースツリー(relaxed graceful tree)に関する改良限界

Improved Bounds for Relaxed Graceful Trees

著者 (2件)： BARRIENTOS Christian (Clayton State Univ., GA, USA) ,  KROP Elliot (Clayton State Univ., GA, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 2  ページ： 287-305  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Rosaによって1966年に定式化(参考文献10)されたグレースツリー予測(GTC)は,グラフラベリングで,ほとんどの疑問と結果の原点としての役割を演じている。今日では,Gallianの調査(参考文献6)が,その根源としてのGTCを主張できるほとんどの基準を示している。n個の頂点に関するツリーをTとし,その付帯的な頂点のラベルの絶対差として端部上の重みを定義した。本稿では,ツリーの過剰度の概念を導入し,領域緩和と端部緩和のグレースラベリング両方に関する領域限界を改良するのに使った。このことは,ε=1/2のロブスタ(lobster)に関するVan Busselの疑問に答えることを可能にした。ロブスタに関連した著者等の最終結果では,過剰度の解析によって得たゲレースサイズ(gracesize)を僅か改良するために,Broersma-Hoedeラベリングを使った。

シソーラス用語： グラフ理論 ,  *木【グラフ】 ,  *状態推定 ,  *標識 ,  端部 ,  頂点 ,  緩和現象
準シソーラス用語： *グラフラベリング ,  *状態予測

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

引用文献 (15件)：

• Bermond, J.-C.: Graceful graphs, radio antennae, and French windmills. In: Wilson, R.J. (ed.) Graph Theory and Combinatorics, pp. 18-37. Pitman Publishing Ltd., London (1979)
• Bonnington, C.P., Širáň, J.: Bipartite labeling of trees with maximum degree three. J. Graph Theory 31(1), 7-15 (1999)
• Brankovic, L., Rosa, A., Širáň, J.: Labellings of trees with maximum degree three-an improved bound. J. Combin. Math. Combin. Comput. 55, 159-169 (2005)
• Broersma, H.J., Hoede, C.: Another equivalent of the graceful tree conjecture. Ars Combin. 51, 183-192 (1999)
• Burzio, M., Ferrarese, G.: The subdivision graph of a graceful tree is a graceful tree. Discrete Math. 181, 275-281 (1998)

タイトルに関連する用語 (1件)： 限界