Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651294 | Discrete Mathematics | 2006 | 6 Pages |
Abstract
We prove a sufficient condition for a graph G to have a matching that interconnects all the components of a disconnected spanning subgraph of G. The condition is derived from a recent extension of the Matroid intersection theorem due to Aharoni and Berger. We apply the result to the problem of the existence of a (spanning) 2-walk in sufficiently tough graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
TomáÅ¡ Kaiser,