What type of study is this?

This is a Quantitative Study study.

October 16, 2025Open Access

Realizing degree sequences with S₃-connected graphs

Key Points

Every graphic sequence with a minimum degree of at least 4 can be realized as an S3-connected graph, ensuring strong connectivity.
A necessary condition for graphic sequences to be S3-connected is that the sum of degrees should be at least 6n - 4, where n is the number of vertices.
Graphic sequences with a minimum degree of 6 lead to graphs that confirm the flow index is strictly less than three.
These findings support the conjecture that all 6-edge-connected graphs have a flow index strictly less than three.

Abstract

A graph G is S₃-connected if, for any mapping: V (G) Z₃ with ₕ ₕ (₆) (v) 03, there exists a strongly connected orientation D satisfying d^+D (v) -d^-D (v) (v) 3 for any v V (G). It is known that S₃-connected graphs are contractible configurations for the property of flow index strictly less than three. In this paper, we provide a complete characterization of graphic sequences that have an S₃-connected realization: A graphic sequence = (d₁, \, , \, dₙ) has an S₃-connected realization if and only if \d₁, \, , \, dₙ\ 4 and ⁿ₈=₁dᵢ 6n - 4. Consequently, every graphic sequence = (d₁, \, , \, dₙ) with \d₁, \, , \, dₙ\ 6 has a realization G with flow index strictly less than three. This supports a conjecture of Li, Thomassen, Wu and Zhang European J. Combin. , 70 (2018) 164-177 that every 6-edge-connected graph has flow index strictly less than three.

Realizing degree sequences with S₃-connected graphs

Key Points

Abstract

Cite This Study