Maximum independent sets in a proper monograph determined through a signature

Abstract

Let G = (V, E) be a non-empty, finite graph. If the vertices of G can be bijectively labeled by a set S of positive distinct real numbers with two vertices being adjacent if and only if the positive difference of the corresponding labels is in S, then G is called a proper monograph. The set S is called the signature of G and denoted as G(S). Not all proper monographs have the property that a set of idle vertices can be bijectively mapped to the maximum independent sets. As a result, in this paper, we present the proper monograph labelings of several classes of graphs that satisfy the property mentioned above. We present the proper monograph labelings of graphs such as cycles, Cn J K1, cycles with paths attached to one or more vertices, and Cycles with an irreducible tree attached to one or more vertices. © World Scientific Publishing Company.