PSD-throttling on Trees

Michael S. Ross

Published 2019-06-14Version 1

PSD-forcing is a coloring process on a graph that colors vertices blue by starting with an initial set $B$ of blue vertices and applying a color change rule (CCR-$\Zp$). The PSD-throttling number is the minimum of the sum of the cardinality of $B$ and the number of the time-steps needed to color the graph (the PSD-propagation time of $B$). Concentration, which is a technique for computing the PSD-throttling number by reducing a tree to a smaller vertex-weighted tree, is introduced and used to determine the PSD-throttling numbers of balanced spiders. It is shown that the PSD-throttling number of a balanced spider does not exceed that of the path of the same order.