pipette
ESEspañol

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

Victor N. Schv\"ollner

Preprint

In the authors' words

The 2-switch-degree of a graph is the number of 2-switches that can be performed on ; equivalently, it is the degree of as a vertex of the realization graph of its degree sequence . 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 from a single one of its local degrees: if has a realization with , then is vertex-transitive and -regular if and only if neither nor is an induced subgraph of . Moreover, for every some prime graph of degree carries a 2-switch raising its degree to . As a further consequence, up to isomorphism there are only 10 realization graphs of prime graphs with degree at most 4.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.