Characterizations and Structure of Sequential Graphs

Abstract

A sequential labeling of a simple graph G (non-tree) with m edges is an injective labeling f such that the vertex labels \(f(x)\) are from \({0,1,…,m-1}\) and the edge labels induced by \(f(x) + f(y)\) for each edge \(xy\) are distinct consecutive positive integers. A graph is sequential if it has a sequential labeling. We give some properties of sequential labeling and the criterion to verify sequential labeling. Necessary and sufficient conditions are obtained for every case of sequential graphs. A complete characterization of non-tree sequential graphs is obtained by vertex closure. Also, characterizations of sequential trees are given. The structure of sequential graphs is revealed.