Spanning k-Trees of n-Connected Graphs |
| |
Authors: | Mikio Kano Hiroo Kishimoto |
| |
Institution: | 1. Department of Computer and Information Sciences, Ibaraki University, Hitachi, Ibaraki, 316-8511, Japan
|
| |
Abstract: | A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg
G
(u) + deg
G
(v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|