DMGT

Discussiones Mathematicae Graph Theory 28(1) (2008) 97-107
DOI: https://doi.org/10.7151/dmgt.1394

PARTITIONS OF A GRAPH INTO CYCLES CONTAINING A SPECIFIED LINEAR FOREST

Ryota Matsubara

Department of Mathematical Information Science
Tokyo University of Science
Tokyo 162-8601, Japan
e-mail: qq8c6dt9n@able.ocn.ne.jp

Hajime Matsumura

Kyoto Computer Gakuin
Kyoto 601-8407, Japan
e-mail: h_matsumura@kcg.ac.jp

Abstract

In this note, we consider the partition of a graph into cycles containing a specified linear forest. Minimum degree and degree sum conditions are given, which are best possible.

Keywords: partition of a graph, vertex-disjoint cycle, 2-factor, linear forest.

2000 Mathematics Subject Classification: 05C38, 05C99.

References

[1]	S. Brandt, G. Chen, R.J. Faudree, R.J. Gould and L. Lesniak, Degree conditions for 2-factors, J. Graph Theory 24 (1997) 165-173, doi: 10.1002/(SICI)1097-0118(199702)24:2<165::AID-JGT4>3.0.CO;2-O.
[2]	G. Chartrand and L. Lesniak, Graphs & Digraphs, 4th edition (Chapman & Hall, London, 2004).
[3]	Y. Egawa, H. Enomoto, R.J. Faudree, H. Li and I. Schiermeyer, Two factors each component of which contains a specified vertex, J. Graph Theory 43 (2003) 188-198, doi: 10.1002/jgt.10113.
[4]	Y. Egawa, R.J. Faudree, E. Györi, Y. Ishigami, R.H. Schelp and H. Wang, Vertex-disjoint cycles containing specified edges, Graphs Combin. 16 (2000) 81-92, doi: 10.1007/s003730050005.
[5]	Y. Egawa and R. Matsubara, Vertex-disjoint cycles containing specified vertices in a graph, AKCE Int. J. Graphs Comb. 3 (1) (2006) 65-92.
[6]	H. Enomoto, Graph partition problems into cycles and paths, Discrete Math. 233 (2001) 93-101, doi: 10.1016/S0012-365X(00)00229-6.
[7]	H. Enomoto and H. Matsumura, Cycle-partition of a graph with specified vertices and edges, to appear in Ars Combinatoria.
[8]	Y. Ishigami and H. Wang, An extension of a theorem on cycles containing specified independent edges, Discrete Math. 245 (2002) 127-137, doi: 10.1016/S0012-365X(01)00137-6.
[9]	A. Kaneko and K. Yoshimoto, On a 2-factor with a specified edge in a graph satisfying the Ore condition, Discrete Math. 257 (2002) 445-461, doi: 10.1016/S0012-365X(02)00506-X.
[10]	R. Matsubara and T. Sakai, Cycles and degenerate cycles through specified vertices, Far East J. Appl. Math. 20 (2005) 201-208.
[11]	T. Sakai, Degree-sum conditions for graphs to have 2-factors with cycles through specified vertices, SUT J. Math. 38 (2002) 211-222.

Received 2 October 2006
Revised 5 February 2007
Accepted 5 February 2007