Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs
Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs
复制标题
无爪图中 2 因子最小分量数的尖锐上界
DOI：
10.1007/s00373-009-0855-7
复制
发表时间：
2009
影响因子：
0.7
通讯作者：
Broersma H
中科院分区：
文献类型：
--
作者：
Broersma H
设G是一个无爪图，其阶为n且最小度为δ。我们改进了 Faudree 等人的结果。和 Gould & Jacobson，并通过证明以下两个结果解决了两个开放问题。如果 δ = 4，则 G 具有最多 (5n− 14)/18 个分量的 2 因子，除非 G 属于有限类特殊图。如果 δ ≥ 5，则 G 具有最多 (n− 3)/(δ − 1) 个分量的 2 因子，除非 G 是完全图。这些界限是最好的，因为我们不能用更小的商代替 5/18，也不能用 δ 代替 δ − 1。
LetGbe a claw-free graph with ordernand minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, thenGhas a 2-factor with at most (5n− 14)/18 components, unlessGbelongs to a finite class of exceptional graphs. If δ ≥ 5, thenGhas a 2-factor with at most (n− 3)/(δ − 1) components, unlessGis a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace δ − 1 by δ, respectively.