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 α-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