Forced Orientation of Graphs
Babak Farzad, Mohammad Mahdian, E. S. Mahmoodian, Amin Saberi, Bardia Sadri · 2011
The concept of forced orientation of graphs was 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)nS, so that the resulting graph is strongly connected, then that given assignment is said to be extendible to a strong orientation of G. The forced strong orientation number f D (G), with respect to a strong orientation D of G, is the smallest cardinality among the subsets of E(G) to which the assignment of orientations from D, can be uniquely extended to E. We use the term defining set instead of "forced orientation" to be consistent with similar concepts in other combinatorial objects. It is shown that any minimal strong orientation defining set is also smallest. We also study Spec(G), the spectrum of G, as the set of all possible values for f D (G), where D is taken over all strong orientations of G. Key words: Forced orientation, defining set, matroid, strong orientation, unique extension 1