γ-Max Labelings of Graphs with Exterior Major Vertices

Abstract

Let G be a graph of order n and size m. A γ-labeling of G is a one-To-one function / : V(G) → { 0 , 1 , 2 , . . . , m} that induces an edge-labeling f : E(G)→ {1,2,..., m} on G defined by f ( e ) = |f/(ii) - f(i>)|, for each edge e = uv i n E ( G ) . The value of f is defined as val(f) = f(e ) • The maximum value of a γ-labeling of G is defined as valmax(G) = inax{val(f) | f is a γ-labeling of G}. For a γ-labeling f of a graph G, a γ-orientation D{f) of / is an oriented graph derived from a γ-labeling f of G, by assigning to each edge xy the orientation (x, y) if f ( x ) < f(y). A vertex of degree at least 3 in a graph G is called a major vertex. The major degree ina(G) of a graph G is the number of major vertices of G. An end-vertex z of G is said to be a terminal vertex of a major vertex v of G if d(z, v) < d(z, w) for every other major vertex w of G. A major vertex v of a graph G is an exterior major vertex of G if it has at least one terminal vertex. In this paper, we characterize a γ-orientation D (f) of a γ-max labeling / of a graph G with exterior major vertices. Furthermore, we determine the maximum value of a γ-labeling of a tree T with a unique exterior major vertex and also a tree T of ma(T) = 2 with adjacent exterior major vertices. © 2018 Charles Babbage Research Centre. All rights reserved.