Article ID Journal Published Year Pages File Type
4651294 Discrete Mathematics 2006 6 Pages PDF
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
,