On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I

Abstract

This paper is mainly concerned with the realizability of a set of n integers as the degrees of vertices of an n-vertex linear graph. Other related problems, such as when a set of integers is realizable as a connected graph, connected graph without “parallel” elements, separable graph, and nonseparable graph, are considered. The relationship between this problem and the problem of isomers in the organic chemistry is described. A similar problem in weighted graphs is also studied.