|
|||||
|
|
Closure and Spanning k-Trees |
|
| Authors: | Ryota Matsubara Masao Tsugaki Tomoki Yamashita |
| Institution: | 1. College of Engineering, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama-shi, Saitama, 337-8570, Japan 2. Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo, 162-8601, Japan 3. Department of Mathematics, Kinki University, Kowakae 3-4-1, Higashi-Osaka, Osaka, 577-8502, Japan |
| Abstract: | In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that \({\sum_{w \in S}d_G(w) \geq |V(G)| -1}\) for every independent set S in G of order k with \({u,v \in S}\) . Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win’s result (Abh Math Sem Univ Hamburg, 43:263–267, 1975) and Kano and Kishimoto’s result (Graph Comb, 2013) as corollaries. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |