Christian Barrientos - Department of Mathematics, Valencia College, Orlando, FL ۳۲۸۳۲, U. S. A.
Maged Youssef - Department of Mathematics & Statistics, College of Sciences, Imam Mohammad Ibn Saud Islamic University, Riyadh ۱۱۶۲۳, Saudi Arabia

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.

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