The generalized Kaneko theorem

Abstract

The following problem was first studied by Kaneko: which simple, connected graphs have vertex disjoint paths of length at least 2, that altogether cover all the vertices of the graph. He gave a good characterization to the problem. Hell and Kirkpatrick observed that a possible generalization of the problem of Kaneko is to characterize those graphs which have a spanning forest such that each tree component of this forest has highest degree k for a fixed integer k \geq 1. In this paper we prove a generalization of the theorem of Kaneko in this sense, show an algorithm solving the generalized problem and prove a Berge-Tutte-type theorem on the minimum number of nodes which are missed by a tree packing.

We can solve the following problem too: given two bounds l,u: V(G) \rightarrow N, does G have a spanning subgraph having degrees at most u such that each component of this subgraph covers a vertex w the degree of which in this component is at least l(w). Many known and new results follow from this formulation.

Bibtex entry:

@techreport{egres-02-09,
AUTHOR = {Szab{\'o}, J{\'a}cint},
TITLE = {The generalized Kaneko theorem},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-09}
}