DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 249
DOI: 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 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