Path coverings of the vertices of a tree |
| |
Authors: | Peter J. Slater |
| |
Affiliation: | Applied Mathematics Division 5641, Sandia Laboratories, Albuquerque, NM 87185, USA |
| |
Abstract: | Consider a collection of disjoint paths in graph G such that every vertex is on one of these paths. The size of the smallest such collection is denoted i(G). A procedure for forming such collections is established. Restricting attention to trees, the range of values for the sizes of the collections obtained is examined, and a constructive characterization of trees T for which one always obtains a collection of size i(T) is presented. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|