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.
From: Victor Nicolas Schvöllner [view email]
[v1]
Fri, 28 Nov 2025 16:28:26 UTC (29 KB)
[v2]
Sun, 8 Mar 2026 01:28:48 UTC (32 KB)
[v3]
Fri, 31 Jul 2026 18:57:14 UTC (42 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。