Published in

Elsevier, Discrete Mathematics, 1-3(187), p. 171-183, 1998

DOI: 10.1016/s0012-365x(97)00233-1

Links

Tools

Export citation

Search in Google Scholar

On the forced unilateral orientation number of a graph

Journal article published in 1998 by Dana Pascovici ORCID
This paper was not found in any repository, but could be made available legally by the author.
This paper was not found in any repository, but could be made available legally by the author.

Full text: Unavailable

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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.