Abstract
A graph has a unilateral orientation if its edges can be oriented such that for every two vertices u and v there exists either a path from u to v or a path from v to u. If G is a graph with a unilateral orientation, then the forced unilateral orientation number of G is defined to be the minimum cardinality of a subset of the set of edges for which there is an assignment of directions that has a unique extension to a unilateral orientation of G. This paper gives a general lower bound for the forced unilateral orientation number and shows that the unilateral orientation number of a graph of size m, order n, and having edge connectivity 1 is equal to m - n + 2. A few other related problems are discussed.
Original language | English |
---|---|
Pages (from-to) | 171-183 |
Number of pages | 13 |
Journal | Discrete Mathematics |
Volume | 187 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 6 Jun 1998 |
Externally published | Yes |