# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## 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 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.