The 2-switch-degree of a graph

Abstract

In this work, we study the 2-switch-degree of a graph $G$, that is, the degree of $G$ as a vertex of the realization graph $\mathcal{G}(d)$ associated with the degree sequence $d$ of $G$. We characterize the active and inactive vertices of a graph, with special attention to the case of split graphs, which play a central role in this setting by Tyshkevich decomposition. We establish the basic properties of the degree, showing in particular that it is additive with respect to the Tyshkevich composition. We then give an explicit formula for the degree in terms of $2K_2$-subgraphs, $C_4$-subgraphs and triangles, which yields an $O(n^3)$ algorithm for its computation and reveals an unexpected connection with the first and second Zagreb indices from Chemical Graph Theory. Finally, we obtain explicit formulas for the degree of trees and unicyclic graphs, and we show that the subgraph of $\mathcal{G}(d)$, induced by the trees with degree sequence $d$, is regular.

Substantially revised version. Rewritten and shortened following referee comments; corrected the degree formula in Thm 7.5 (yielding an O(n^3) algorithm) and the unicyclic degree formula in Thm 8.6; simplified Sec. 3