ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2019: 0.600
Rejection Rate (2018-2019): c. 84%
Mathematicae Graph Theory 19(2) (1999) 249DOI: 10.7151/dmgt.1100
Department of Geometry and Algebra
Faculty of Science, P.J. Safárik University
Jesenná 5, 041 54 Košice, Slovak Republic
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
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.
Conjecture. Let G be an undirected graph and let nd < 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