Bimagic Vertex Labelings
- PDF / 127,713 Bytes
- 8 Pages / 594 x 792 pts Page_size
- 60 Downloads / 183 Views
BIMAGIC VERTEX LABELINGS Ì. F. Semeniuta,1† S. N. Nedilko,1‡ and V. N. Nedilko1‡
UDC 519.17
Abstract. The notion of the equivalence of vertex labelings on a given graph is introduced. The equivalence of three bimagic labelings for regular graphs is proved. A particular solution is obtained for the problem of the existence of a 1-vertex bimagic vertex labeling of multipartite graphs, namely, for graphs isomorphic with K n ,n ,m . It is proved that the sequence of bi-regular graphs K n ( ij ) = (( K n -1 - M ) + K1 ) - ( un ui ) - ( un u j ) admits 1-vertex bimagic vertex labeling, where ui , u j is any pair of non-adjacent vertices in the graph K n-1 - M , un is a vertex of K1 , M is perfect matching of the complete graph K n-1 . It is established that if an r-regular graph G of order n is distance magic, then graph G + G has a 1-vertex bimagic vertex labeling with magic constants ( n + 1)( n + r ) / 2 + n 2 and ( n + 1)( n + r ) / 2 + nr. Two new types of graphs that do not admit 1-vertex bimagic vertex labelings are defined. Keywords: distance magic labeling, 1-vertex bimagic vertex labeling, odd 1-vertex bimagic vertex labeling, even 1-vertex bimagic vertex labeling. INTRODUCTION Optimal labeling of elements of a graph is a classical discrete optimization problem. For a review of publications in different types of labeling, see Gallian’s electronic journal [1], which is updated every year. The concept of graph labeling is wider than coloring and has two important differences. First, injective (or bijective) function is used in labeling; it associates different numbers with different elements of the graph, and normal color constraints are replaced with relations between labels. This predetermines the second difference: the constraints include arithmetic calculations with numerical values of the labels. Mathematical models with the use of labeled graphs are widely applied in the coding theory, in particular, to construct synchronization codes and convolution codes with optimal properties of autocorrelation, codes for radiolocation, on the basis of the Skolem sequence [2], to solve the uncertainty problem in X-ray crystallography, and to design communication networks [3–5]. For example, graceful labeling of trees is applied in routing algorithms in MPLS Network [6]. The mathematical apparatus of the labeling theory often appears to be useful to provide additional information about the graph. For example, the paper [7] considers the possibility of calculating the distance between any pairs of vertices of a graph under the presence of vertex labeling and without involving another additional information about the graph. Distance magic labeling and its variations can be applied as mathematical models to solve optimal planning problems, in particular, in planning incomplete tournaments with different properties [8, 9]. In the present paper, we will consider vertex labelings, which are a combination of magic and distance labelings. We will analyze the equivalence of three types of bimagic labeling proposed in [10]. We w
Data Loading...
