Forced Orientation of Graphs
Filed in: Combinatorics
Babak Farzad, Amin Saberi, Ebad S. Mahmoodian, and Mohammad Mahdian, and Bardia Sadri
The concept of forced orientation of graphs was first introduced by G. Chartrand et al. in 1994. If, for a given assignment of directions to a subset S of the edges of a graph G, there exists an orientation of E(G) - S, such that the resulting graph is strongly connected, then that given assignment is said to be extendible to a strong orientation of G. A forcing set for a strong orientation D of G is a subset of edges of G, for which the assignment of orientations from D, can uniquely be extended to all edges, reproducing D. We denote the size of the smallest forcing set for a strong orientation D of G by fD(G). The main result of this paper shows that all minimal forcing sets for any particular strong orientation D of G have the same cardinality. We also characterize those graphs G that have strong orientations D, for which fD(G) is equal to the trivial maximum of |E(G)|.
Bulletin of Iranian Mathematical Society, Vol 32, No 1, 2006. [PDF]
The concept of forced orientation of graphs was first introduced by G. Chartrand et al. in 1994. If, for a given assignment of directions to a subset S of the edges of a graph G, there exists an orientation of E(G) - S, such that the resulting graph is strongly connected, then that given assignment is said to be extendible to a strong orientation of G. A forcing set for a strong orientation D of G is a subset of edges of G, for which the assignment of orientations from D, can uniquely be extended to all edges, reproducing D. We denote the size of the smallest forcing set for a strong orientation D of G by fD(G). The main result of this paper shows that all minimal forcing sets for any particular strong orientation D of G have the same cardinality. We also characterize those graphs G that have strong orientations D, for which fD(G) is equal to the trivial maximum of |E(G)|.
Bulletin of Iranian Mathematical Society, Vol 32, No 1, 2006. [PDF]