Characterizations of graphs having orientations satisfying local degree restrictions
Roger C. Entringer, L. Kirk Tolman · Czechoslovak Mathematical Journal · 1978
Throughout the short history of graph theory several authors have discussed problems concerning orientations of undirected graphs.These have included, for example, enumeration of the number of orientations of given undirected graphs as dealt with in the monograph of F. HARARY and E. M. PALMER [14] (some of these results also appear in [13]).However the type of problems most frequently considered are all special instances of the following. Problem. Given a property P that oriented [antisymmetric) graphs may possess, characterize those undirected [symmetric) graphs having an orientation with property P.Our purpose in this article is twofold; we first wish to provide a convenient reference to and show the interdependence between the many results and open questions concerning graph orientation problems and secondly, we wish to add to this body of information through consideration of a specific orientation problem.The problem is that of characterizing those graphs having an orientation D in which the outdegree and indegree of each point pj of D satisfy rj ^ od{pj) ^ 5^ and Uj ^ id(py) й Vj respectively for a specified collection {(гр Sj, Uj, Vj)} of 4-tuples of non-negative integers. TERMINOLOGYIn this section we make precise some of the terminology we will use throughout the remainder of the paper.Any term used later without definition will have the meaning given in [U] or [12].A walk of an undirected (directed) graph is a sequence of points Pi, .-,Pn in which each PiPi+i, i = 1, ...,n -1, is a line (arc) of the graph.If pi == p" the walk is