Optimal maximal graphs

An optimal labeling of a graph with n vertices and m edges is an injective assignment of the first n nonnegative integers to the vertices‎, ‎that induces‎, ‎for each edge‎, ‎a weight given by the sum of the labels of its end-vertices with the property that the set of all induced weights consists of the first m positive integers‎. ‎We explore the connection of this labeling with other well-known functions such as super edge-magic and \alpha-labelings‎. ‎A graph with n vertices is maximal when the number of edges is ۲n-۳; all the results included in this work are about maximal graphs‎. ‎We determine the number of optimally labeled graphs using the adjacency matrix‎. ‎Several techniques to construct maximal graphs that admit an optimal labeling are introduced as well as a family of outerplanar graphs that can be labeled in this form.

Keywords:

‎Optimal labeling‎ , ‎maximal graph‎ , ‎additive labeling