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


An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets
Authors:Wanpeng LEI  Liming XIONG  Junfeng DU  Jun YIN
Affiliation:School of Mathematics and Statistics, Beijing Institute of Technology,Beijing 100081, China.,School of Mathematics and Statistics, Beijing Institute of Technology,Beijing 100081, China.,School of Mathematics and Statistics, Beijing Institute of Technology,Beijing 100081, China. and School of Computer Science, Qinghai Normal University,Xining 810008, Qinghai, China.
Abstract:Win proved a well-known result that the graph $G$ of connectivity$kappa(G)$ with $alpha(G) leq kappa(G) + k - 1$ $(kgeq2)$ has aspanning $k$-ended tree, i.e., a spanning tree with at most $k$leaves. In this paper, the authors extended the Win theorem in casewhen $kappa(G)=1$ to the following: Let $G$ be a simple connectedgraph of order large enough such that $alpha(G)leq k+1$ $(kgeq3)$and such that the number of maximum independent sets of cardinality$k+1$ is at most $n-2k-2$. Then $G$ has a spanning $k$-ended tree.
Keywords:$k$-ended tree   Connectivity   Maximum independent set
本文献已被 CNKI SpringerLink 等数据库收录!
点击此处可从《数学年刊B辑(英文版)》浏览原始摘要信息
点击此处可从《数学年刊B辑(英文版)》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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