Covering cycles and \(k\)-term degree sums. (English) Zbl 0857.05058
Summary: We show that if \(\sum_{x\in S} \deg_Gx\geq |G|\), for every stable set \(S\subseteq V(G)\), \(|S|= k\), then the vertex set of \(G\) can be covered with \(k-1\) cycles, edges or vertices. This settles a conjecture by H. Enomoto, A. Kaneko and Zs. Tuza [Colloq. Math. Soc. János Bolyai 52, 213-220 (1988; Zbl 0723.05100)].
MSC:
| 05C38 | Paths and cycles |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Citations:
Zbl 0723.05100References:
| [1] | G. A. Dirac: Some theorems on abstract graphs,Proc. London Math. Soc.,2 (1952), 69-81. · Zbl 0047.17001 · doi:10.1112/plms/s3-2.1.69 |
| [2] | H. Enomoto, A. Kaneko, M. Kouider andZs. Tuza: Degree sums and covering cycles,Journal of Graph Theory,20 (1995), 419-422. · Zbl 0837.05086 · doi:10.1002/jgt.3190200405 |
| [3] | H. Enomoto, A. Kaneko, andZs. Tuza:P 3-factors and covering cycles in graphs of minimum degreen/3, Colloquia Mathematica Societatis J?nos Bolyai 52. Combinatorics, Eger (Hungary), North Holland (1988), 213-220. |
| [4] | M. Kouider: Covering vertices by cycles,Journal of Graph Theory,18 (1994), 757-776. · Zbl 0816.05046 · doi:10.1002/jgt.3190180802 |
| [5] | O. Ore: Note on Hamiltonian circuits,Amer. Math. Monthly,67 (1960), 55. · Zbl 0089.39505 · doi:10.2307/2308928 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
