Classification of prime graphs with 2-switch-degree at most 4
En palabras de los autores
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.
Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.