On strongly connected orientations of graphs
Matúš Harminc · Discussiones Mathematicae Graph Theory · 1999
We consider finite, loopless graphs or digraphs, without multiple edges or arcs (with no pairs of opposite arcs). Let G = (V,E) be a graph. A digraph D = (V,A) is an orientation of G if A is created from E by replacing every edge of E by an arc in one direction. Let nd denote the number of vertices with the degree d in G. By the degree pair of a vertex v ∈ V in D the ordered pair [outdegree(v), indegree(v)] is meant. It is easy to see that if there exists a strongly connected orientation D of a graph G with pairwise different degree pairs of vertices in D then in G we have nd < d for every positive integer d.