Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T14:43:56.731Z Has data issue: false hasContentIssue false
  • English
  • Français

Cycle Partitions in Graphs

Published online by Cambridge University Press:  12 September 2008

C. C. Chen  and
G. P. Jin
C. C. Chen
Affiliation:
Department of Mathematics, National University of Singapore, Kent Ridge, Singapore0511
G. P. Jin
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we prove that every graph contains a cycle intersecting all maximum independent sets. Using this, we further prove that every graph with stability number α is spanned by α disjoint cycles. Here, the empty set, the graph of order 1 and the path of order 2 are all considered as degenerate cycles.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 2 , June 1996 , pp. 95 - 97
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Berge, B. (1983) Path partitions in directed graphs. Ann. Discrete Math. 17 59–63.Google Scholar
[2]Bondy, J. A. (to appear) A Short Proof of the Chen-Manalastas Theorem.Google Scholar
[3]Chen, C. C. and Manalastas, P. Jr. (1983) Every finite strongly connected digraph of stability 2 has a Hamiltonian path. Discrete Math. 44 243–250.CrossRefGoogle Scholar
[4]Gallai, T. (1964) Problem 15. In: Fielder, M. (ed.), Theory of Graphs and its Applications, Czech Academy of Science Publication, 161.Google Scholar
[5]Gallai, T. and Milgram, A. N. (1960) Verallgemeinerung eines graphentheoretischen Satzes von Rédei. Acta Sci. Math. Szeged 21 181–186.Google Scholar
[6]Rédei, L. (1934) Ein kombinatorischer Satz. Acta Litt. Szeged 7 39–43.Google Scholar