Magic Graphの一般化とその性質

IPSJ

Bibliographic Information

Other Title
  • Generalization of Magic Graphs and Their Properties

Search this article

Abstract

与えられたグラフの頂点や辺に数字を配置して，辺とその両端の頂点または頂点につながるすべての辺の数字の和が一定になるとき，その和を定和，そのグラフをmagic graph，その数字の配置をmagic labelingと呼ぶ．数字の和が一定となる配置はグラフに対する魔方陣と見ることもできる．従来のmagic graphの研究では辺や頂点に配置する数字の個数は1個のみであった．本論文では辺や頂点に配置する数字の個数を1個に限定しない一般化したmagic graphを提案しその性質を述べる．定和が満たす定和方程式を定式化し，それを用いてある条件を満たすグラフにmagic labelingが存在しないことを示す．多角形（Ck）や正多面体などの次数一定の正則グラフに対して最大・最小定和の計算式を導出し，ある条件を満たすグラフに最大・最小定和を持つmagic labelingが存在しないことを示す．さらに与えられたmagic graphの変換と合成の概念を述べ，アフィン変換によるmagic labelingの双対性，漸化的な構成方法，を述べる．

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.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top