On the forced unilateral orientation number of a graph

Dana Pascovici*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)171-183
Number of pages13
JournalDiscrete Mathematics
Volume187
Issue number1-3
DOIs
Publication statusPublished - 6 Jun 1998
Externally publishedYes

Fingerprint

Dive into the research topics of 'On the forced unilateral orientation number of a graph'. Together they form a unique fingerprint.

Cite this