Classification of prime graphs with 2-switch-degree at most 4

Abstract

The 2-switch-degree deg(G) of a graph G is the number of 2-switches that can be performed on G; equivalently, it is the degree of G as a vertex of the realization graph 𝒢(d) of its degree sequence d. We classify the prime graphs of 2-switch-degree at most 4, where a graph is prime if it is indecomposable with respect to the Tyshkevich composition and every vertex takes part in some 2-switch. From this classification we derive a sharp dichotomy that recovers the global shape of 𝒢(d) from a single one of its local degrees: if d has a realization X with deg(X)=k≤3, then 𝒢(d) is vertex-transitive and k-regular if and only if neither T₂₂₁ nor T₂₂₁̅ is an induced subgraph of X. Moreover, for every k≥ 4 some prime graph of degree k carries a 2-switch raising its degree to 2k−2. As a further consequence, up to isomorphism there are only 10 realization graphs of prime graphs with degree at most 4.

Tuza's Conjecture for Graphs of Maximum Degree at Most 10
Amrit Kandasamy
arXiv11 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
Selberg sieve weights and sign changes of Kloosterman sums. II. Square-free moduli with at most four prime factors
Yixiu Xiao, Hongze Li
arXiv21 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
e-Positive caterpillars have maximum degree at most three
Davion Q. B. Tang, David G. L. Wang, Monica M. Y. Wang
arXiv29 Oct 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Hilbert schemes of low-degree rational curves on a prime Fano threefold of degree $22$
Kiryong Chung, Dae-Won Lee
arXiv8 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Hitchin's Conjecture for sl_n in Odd Prime Degree
Boming Jia
arXiv10 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{schvollner2026classification,
  title = {{Classification of prime graphs with 2-switch-degree at most 4}},
  author = {Victor N. Schvöllner},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40274},
  eprint = {2609.40274},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40274},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Classification of prime graphs with 2-switch-degree at most 4
AU  - Victor N. Schvöllner
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40274
UR  - https://arxiv.org/abs/2609.40274
AB  - The 2-switch-degree deg(G) of a graph G is the number of 2-switches that can be performed on G; equivalently, it is the degree of G as a vertex of the realization graph 𝒢(d) of its degree sequence d. We classify the prime graphs of 2-switch-degree at most 4, where a graph is prime if it is indecomposable with respect to the Tyshkevich composition and every vertex takes part in some 2-switch. From this classification we derive a sharp dichotomy that recovers the global shape of 𝒢(d) from a single one of its local degrees: if d has a realization X with deg(X)=k≤3, then 𝒢(d) is vertex-transitive and k-regular if and only if neither T_221 nor T_221̅ is an induced subgraph of X. Moreover, for every k≥ 4 some prime graph of degree k carries a 2-switch raising its degree to 2k−2. As a further consequence, up to isomorphism there are only 10 realization graphs of prime graphs with degree at most 4.
ER  -

Abstract

Related

Cite