Mathematics – Combinatorics
Scientific paper
2005-11-28
Mathematics
Combinatorics
Minor rephrasing, new pictures, 14 pages
Scientific paper
Consider a graph whose edges have been colored red and blue. Assign a nonnegative real weight to every edge so that at every vertex, the sum of the weights of the incident red edges equals the sum of the weights of the incident blue edges. The set of all such assignments forms a convex polyhedral cone in the edge space, called the \emph{alternating cone}. The integral (respectively, $\{0,1\}$) vectors in the alternating cone are sums of characteristic vectors of closed alternating walks (respectively, trails). We study the basic properties of the alternating cone, determine its dimension and extreme rays, and relate its dimension to the majorization order on degree sequences. We consider whether the alternating cone has integral vectors in a given box, and use residual graph techniques to reduce this problem to searching for a closed alternating trail through a given edge. The latter problem, called alternating reachability, is solved in a companion paper along with related results.
Bhattacharya Amitava
Peled Uri N.
Srinivasan Murali K.
No associations
LandOfFree
Cones of closed alternating walks and trails 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 Cones of closed alternating walks and trails, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cones of closed alternating walks and trails will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-715702