Back to Search
Start Over
Graphs with no K3,3 Minor Containing a Fixed Edge.
- Source :
-
International Journal of Combinatorics . 2013, p1-7. 7p. - Publication Year :
- 2013
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 16879163
- Database :
- Academic Search Index
- Journal :
- International Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 95071462
- Full Text :
- https://doi.org/10.1155/2013/783710