Spanning trees and spanning closed walks with small degrees |
| |
Affiliation: | Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran |
| |
Abstract: | Let G be a graph and let f be a positive integer-valued function on . In this paper, we show that if for all , , then G has a spanning tree T containing an arbitrary given matching such that for each vertex v, , where denotes the number of components of and denotes the number of components of the induced subgraph with the vertex set S. This is an improvement of several results. Next, we prove that if for all , , then G admits a spanning closed walk passing through the edges of an arbitrary given matching meeting each vertex v at most times. This result solves a long-standing conjecture due to Jackson and Wormald (1990). |
| |
Keywords: | Spanning tree Spanning closed walk Toughness Connected factor Matching |
本文献已被 ScienceDirect 等数据库收录! |
|