Group Labeling of some Graphs
- PDF / 148,311 Bytes
- 9 Pages / 594 x 792 pts Page_size
- 36 Downloads / 226 Views
GROUP LABELING OF SOME GRAPHS Ì. F. Semeniuta1 and G. A. Donets2
UDC 519.1
Abstract. Group labelings of magic and antimagic types are analyzed and relationship between them for the graph and its complement are established. The concept of closed group distance magic labeling is introduced. The existence conditions for Z 2m -distance magic labeling of the graph C 4m 2 are found, and a method for its construction is proposed. The existence conditions for Z r2 -distance magic and antimagic labelings of the Cartesian product of regular graphs are established. The results of group remote magic labeling of the connection of two graphs are obtained. Keywords: D-distance magic labeling, group distance magic labeling, group distance antimagic labeling. INTRODUCTION Models based on labeled graphs are efficiently applied in theoretical studies related to the analysis of decompositions of graphs and algebraic combinatorial structures, as well as in mapping theory. Among practical applications, noteworthy are cryptography, network planning, database management, radio astronomy, and biocomputer science. Graph labeling is understood as injective or bijective mapping of the set of elements of the graph into the set of numbers satisfying certain conditions that influence labeling type. In the paper, we will analyze group labelings of magic and antimagic types. Sedlacek [1] with his report at the symposium in Smolenice in 1963 was the first to introduce the concept of magic graph. He called a graph magic if its edges are associated with real numbers so that the sum of labels of edges incident to the vertex remains constant irrespective of vertex choice. In [2], Stewart established a constraint for the set of rib labels by proposing to use serial integers and introduced the term “supermagic” for the appropriate rib labeling. Kotzig and Rosa [3] defined total magic labeling of graph G = (V , E ) as a bijective mapping j of set V È E onto the set of numbers 1, 2, K , | V | + | E | such that the sum of labels of an edge and its two incident vertices is equal to a constant. Such labeling was later called rib–magic one [4]. Lih extended this concept to planar graphs, with labels also associated with edges [5]. If for the mapping described above j the sum of labels of a vertex and of edges incident to it is constant for each vertex of the graph, then its vertex-magic labeling [6] is considered. The results of solution of problems of existence, creation, and enumeration of graph labelings are presented in the electronic log A Dynamic Survey of Graph Labelling edited by Gallian [7]. This log also describes other kinds of magic labelings. Among them are D-distance magic labeling proposed by O’Neal and Slater [8] and its more weak version: group distance magic labeling introduced by Froncek [9]. Graph labelings by group elements were considered from different points of view. Fukuchi [10] and Egawa [11] analyzed vertex labelings of graphs by elements of Abelian groups where connected components of the graph are of constant weight. Combe, Nelso
Data Loading...
