Title

The 2-Star Spectrum of Stars

Document Type

Article

Publication Date

10-1-2009

Description

Let K be a family of graphs. A K-decomposition, D,of a graph H (called the host) is a partition of the edges of H such that the subgraph induced by each part of the partition (called blocks) is isomorphic to an element of K. The chromatic index of the decomposition, denoted x'(D), is the minimum number of colors required to color each block in the decomposition so that blocks that share a common node in H receive different colors. The K-spectrum of H, denoted SpecK (H), is the set of all values of x'(D) over all possible K-decompositions of H. In this paper, we will show that any n-element subset of the positive integers is the spectrum of a tree when decomposing into a family of n trees. We will also look at ways of improving this result. In particular, we examine the problem of whether any n-element subset of positive integers is the spectrum of a star when decomposing into other stars. These results often have a number theoretical flavor to them, as they deal strictly with the parameters involved and not the underlying graphs.

This document is currently not available here.

COinS