Discussiones Mathematicae Graph Theory 19(2) (1999) 249
DOI: https://doi.org/10.7151/dmgt.1100

ON STRONGLY CONNECTED ORIENTATIONS OF GRAPHS

Matús Harminc

Department of Geometry and Algebra
Faculty of Science, P.J. Safárik University
Jesenná 5, 041 54 Košice, Slovak Republic
e-mail: harminc@duro.upjs.sk

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 n_d 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 n_d < d for every positive integer d.

Conjecture. Let G be an undirected graph and let n_d < d for every positive integer d. Then there exists a strongly connected orientation D of G with pairwise different degree pairs of vertices.

Received 2 February 1999
Revised 7 October 1999