Magic Graphの一般化とその性質

• Item type: Journal(1)
• 公開日: 2018-06-15
• タイトル: Magic Graphの一般化とその性質
• タイトル / 言語: en
• タイトル: Generalization of Magic Graphs and Their Properties
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] グラフラベリング，マジックラベリング，エッジマジック，魔方陣，パズル
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 会津大学コンピュータ理工学部
• 著者所属(英): en
• 著者所属(英): The University of Aizu
• 著者名: 杉山, 雅英
• 著者名(英): Masahide, Sugiyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 与えられたグラフの頂点や辺に数字を配置して，辺とその両端の頂点または頂点につながるすべての辺の数字の和が一定になるとき，その和を定和，そのグラフをmagic graph，その数字の配置をmagic labelingと呼ぶ．数字の和が一定となる配置はグラフに対する魔方陣と見ることもできる．従来のmagic graphの研究では辺や頂点に配置する数字の個数は1個のみであった．本論文では辺や頂点に配置する数字の個数を1個に限定しない一般化したmagic graphを提案しその性質を述べる．定和が満たす定和方程式を定式化し，それを用いてある条件を満たすグラフにmagic labelingが存在しないことを示す．多角形（Ck）や正多面体などの次数一定の正則グラフに対して最大・最小定和の計算式を導出し，ある条件を満たすグラフに最大・最小定和を持つmagic labelingが存在しないことを示す．さらに与えられたmagic graphの変換と合成の概念を述べ，アフィン変換によるmagic labelingの双対性，漸化的な構成方法，を述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: When the vertices and edges in a given graph are labeled with positive integers and all edges connected to a vertex (or an edge and two connecting vertices) have a constant sum, it is called a magic sum, and the corresponding labeling and graph are referred to as magic labeling and magic graph, respectively. This problem can be treated as one extension of a magic square. Conventional studies on magic graphs allow at most one number to be assigned to each vertex and edge. This paper proposes a generalized definition of magic graphs, for which any number of digits can be used to label to a vertex and edge, and describes the construction of such magic graphs and their properties. A magic sum equation is formulated and a generalized property for which a magic graph does not exist is proved. An equation for calculating the minimum and maximum magic sums is derived for regular graphs, including polygons and polyhedrons. Furthermore, techniques of transforming and synthesizing magic graphs, duality of magic labeling using an affine transform, and recursive construction are discussed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 59, 号 6, p. 1394-1404, 発行日 2018-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764