Journal of Combinatorics

Volume 3 (2012)

Number 2

Partitioning graphs into paths or cycles of prescribed lengths

Pages: 135 – 161

DOI: https://dx.doi.org/10.4310/JOC.2012.v3.n2.a1

Authors

Colton Magnant (Georgia Southern University, Statesboro, Ga., U.S.A.)

Kenta Ozeki (National Institute for Informatics, Tokyo, Japan)

Abstract

In this paper, we consider the path (and cycle) partition problem for graphs with additional length restrictions. More specifically, we prove sufficient degree sum conditions for the vertices of a graph to be partitioned into paths, with fixed end vertices, such that these paths have approximately prescribed lengths. We also prove similar results for partitions into cycles of approximately prescribed lengths each containing a specified vertex.

Keywords

graph partition, degree sum, path length

2010 Mathematics Subject Classification

Primary 05C70. Secondary 05C35.

Full Text (PDF format)

Published 28 September 2012