We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Graphs with no K<sub>3,3</sub> Minor Containing a Fixed Edge.
- Authors
Wagner, Donald K.
- Abstract
It is well known that every cycle of a graph must intersect every cut in an even number of edges. For planar graphs, Ford and Fulkerson proved that, for any edge e, there exists a cycle containing e that intersects every minimal cut containing e in exactly two edges. The main result of this paper generalizes this result to any nonplanar graph G provided G does not have a K 3,3 minor containing the given edge e. Ford and Fulkerson used their result to provide an efficient algorithm for solving the maximum-flow problem on planar graphs. As a corollary to the main result of this paper, it is shown that the Ford-Fulkerson algorithm naturally extends to this more general class of graphs.
- Subjects
GRAPH theory; PLANAR graphs; EVEN numbers; ALGORITHMS; INTERSECTION graph theory; MATHEMATICS
- Publication
International Journal of Combinatorics, 2013, p1
- ISSN
1687-9163
- Publication type
Article
- DOI
10.1155/2013/783710