Optimal maximal graphs

Abstract

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 $2n-3$; 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