On vertex-magic and edge-magic total injections of graphs

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)

Abstract

The study of graph labellings has focused on finding classes of graphs which admit a particular type of labelling. Here we consider variations of the well-known edge-magic and vertex-magic total labellings for which all graphs admit such a labelling. In particular, we consider two types of injections of the vertices and edges of a graph with positive integers: (1) for every edge the sum of its label and those of its end-vertices is some magic constant (edge-magic); and (2) for every vertex the sum of its label and those of the edges incident to it is some magic constant (vertex-magic). Our aim is to minimise the maximum label or the magic constant associated with the injection. We present upper bounds on these parameters for complete graphs, forests and arbitrary graphs, which in a number of cases are within a constant factor of being optimal. Our results are based on greedy algorithms for computing an antimagic injection, which is then extended to a magic total injection. Of independent interest is our result that every forest has an edge-antimagic vertex labelling.

Original languageEnglish
Pages (from-to)49-63
Number of pages15
JournalAustralasian Journal of Combinatorics
Volume26
Publication statusPublished - 2002
Externally publishedYes

Cite this