Alternating walks in partially 2-edge-colored graphs and optimal strength of graph labeling
✍ Scribed by AndréE. Kézdy; Chi Wang
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 292 KB
- Volume
- 194
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
A graph is partially 2-edge-colored if edges of G are colored by two colors, possibly with some edges uncolored. A walk is alternating in a partially 2-edge-colored graph if the given 2edge-coloring can be extended to all edges of G such that colors alternate as the walk is traversed. We present a polynomial-time algorithm to decide, given a partially 2-edge-colored graph and two distinct vertices, whether there is an altemating walk connecting the two vertices. We apply the algorithm to solve problems in graph labeling. In particular, we show that the regularizable strength of a graph can be determined in polynomial time. (~