|
|
| |
| An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets |
| |
Citation： |
Wanpeng LEI,Liming XIONG,Junfeng DU,Jun YIN.An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets[J].Chinese Annals of Mathematics B,2019,40(3):411~428 |
| Page view： 921
Net amount： 733 |
Authors： |
Wanpeng LEI; Liming XIONG;Junfeng DU;Jun YIN |
Foundation： |
This work was supported by the National Natural Science
Foundation of China (Nos.11871099, 11671037, 11801296) and the
Nature Science Foundation from Qinghai Province (No.2017-ZJ-949Q). |
|
|
| Abstract： |
Win proved a well-known result that the graph $G$ of connectivity
$\kappa(G)$ with $\alpha(G) \leq \kappa(G) + k - 1$ $(k\geq2)$ has a
spanning $k$-ended tree, i.e., a spanning tree with at most $k$
leaves. In this paper, the authors extended the Win theorem in case
when $\kappa(G)=1$ to the following: Let $G$ be a simple connected
graph of order large enough such that $\alpha(G)\leq k+1$ $(k\geq3)$
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 |
Classification： |
05C10 |
|
|
Download PDF Full-Text
|
