|
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 www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2002}, |
| NUMBER | = | {TR-2002-09} |