2-switch: transition and stability on graphs and forests
Daniel Alejandro Jaume, Adrián Pastine, Victor Nicolas Schvöllner · arXiv (Cornell University) · 2020
Given any two forests with the same degree sequence, we show in an algorithmic way that one can be transformed into the other by a sequence of 2-switches in such a way that all the intermediate graphs of the transformation are forests. We also prove that the 2-switch operation perturbs minimally some well-known integer parameters in families of graphs with the same degree sequence. Then, we apply these results to conclude that the studied parameters have the interval property on those families.