首页 | 本学科首页   官方微博 | 高级检索  
     


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 urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0001 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 urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0002. We show that if urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0003 for any nonempty subset urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0004, then a connected graph G has a spanning tree such that urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0005 for all urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0006, where urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0007 is the set of neighbors v of vertices in S with urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0008, urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0009, and urn:x-wiley:03649024:media:jgt21824:jgt21824-math-0010 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
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号