Semeniuta M.F., Nedilko S.N., Nedilko V.N.
Bimagic vertex labelings

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 Kn, n, m. It is proved that the sequence of bi-regular graphs Kn(ij) = ((Kn − 1 − M) + K1) − (unui) − (unuj) admits 1-vertex bimagic vertex labeling, where ui, uj is any pair of non-adjacent vertices in the graph Kn − 1 − M, un is a vertex of K1, M is perfect matching of the complete graph Kn − 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 + n2 and (n + 1)(n + r)/2 + nr. Two new types of graphs that do not admit 1-vertex bimagic vertex labelings are defined. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: 1-vertex bimagic vertex labeling, distance magic labeling, even 1-vertex bimagic vertex labeling, odd 1-vertex bimagic vertex labeling, Graphic methods, Complete graphs, Magic constants, Magic labeling, Multipartite graph, Nonadjacent vertices, Particular solution, Perfect matchings, Vertex labeling, Graph theory

Cite:
Semeniuta M.F., Nedilko S.N., Nedilko V.N. (2018). Bimagic vertex labelings. Cybernetics and Systems Analysis, 54 (5), 100-108. doi: https://doi.org/10.1007/s10559-018-0079-z http://jnas.nbuv.gov.ua/article/UJRN-0000897820 [In Ukrainian].