Equivalence between Extendability and Factor-Criticality
Equivalence between Extendability and Factor-Criticality
复制标题
DOI：
--
复制
发表时间：
2010-11
期刊：
影响因子：
--
通讯作者：
Zan-Bo Zhang;Tao-Ming Wang;Dingjun Lou
中科院分区：
文献类型：
--
作者：
Zan-Bo Zhang;Tao-Ming Wang;Dingjun Lou
本文证明了：如果$k\geq(\nu+2)/4$，其中$\nu$表示一个图的阶数，则一个非二部图$G$是$k$-可扩当且仅当它是$2k$-因子临界的。如果$k\geq(\nu-3)/4$，则图$G$是$k\1/2$-可扩当且仅当它是$(2k+1)$-因子临界图。我们还举例说明了这两个界是最好的。我们的结果回答了Favaron[3]和Yu[11]提出的一个问题。
In this paper, we show that if $k\geq (\nu+2)/4$, where $\nu$ denotes the order of a graph, a non-bipartite graph $G$ is $k$-extendable if and only if it is $2k$-factor-critical. If $k\geq (\nu-3)/4$, a graph $G$ is $k\ 1/2$-extendable if and only if it is $(2k+1)$-factor-critical. We also give examples to show that the two bounds are best possible. Our results are answers to a problem posted by Favaron [3] and Yu [11].