Spanning Trees with Vertices Having Large Degrees |
| |
| Authors: | Yoshimi Egawa Kenta Ozeki |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCE, TOKYO UNIVERSITY OF SCIENCE, SHINJUKU‐KU, TOKYO, JAPAN;2. NATIONAL INSTITUTE OF INFORMATICS, CHIYODA‐KU, TOKYO, JAPAN;3. JST, ERATO, KAWARABAYASHI LARGE GRAPH PROJECT |
| |
| Abstract: | Let G be a connected simple graph, and let f be a mapping from  to the set of integers. This paper is concerned with the existence of a spanning tree in which each vertex v has degree at least  . We show that if  for any nonempty subset  , then a connected graph G has a spanning tree such that  for all  , where  is the set of neighbors v of vertices in S with  ,  , and  is the degree of x in T. This is an improvement of several results, and the condition is best possible. |
| |
| Keywords: | degree constraint spanning trees hall‐type condition 05C05 05C70 |
|
|
