The generalized Kaneko theorem

Jácint Szabó


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:

AUTHOR = {Szab{\'o}, J{\'a}cint},
TITLE = {The generalized Kaneko theorem},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-09}

Last modification: 13.3.2018. Please email your comments to Tamás Király!