Full Orientability of the Square of a Cycle

Details Full Orientability of the Square of a Cycle Full Orientability of the Square of a Cycle

2012-02-26

arxiv.org/abs/1202.5721v1

Mathematics

Combinatorics

7 pages, accepted by Ars Combinatoria on May 26, 2010

Scientific paper

Let D be an acyclic orientation of a simple graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define m and M to be the minimum and the maximum number of d(D) over all acyclic orientations D of G. We call G fully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying m <= k <= M. In this paper, we prove that the square of a cycle C_n of length n is fully orientable except n=6.

Affiliated with

Also associated with

No associations

Rating

Full Orientability of the Square of a Cycle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Full Orientability of the Square of a Cycle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Full Orientability of the Square of a Cycle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-215662